题解 AT5800 【[AGC043C] Giant Graph】
xht
2020-03-22 18:18:23
以下设 $n,m$ 同阶。
由于 $10^{18}$ 非常大，因此求最大独立集，相当于贪心地从权值大的往小的选，能选则选。
考虑 dp，设 $f_{x,y,z}$ 表示点 $(x,y,z)$ 是否要被选。
转移方程为 $f_{x,y,z} = \prod_{(x^\prime,y^\prime,z^\prime) \to (x,y,z)} [f_{x^\prime,y^\prime,z^\prime} = 0]$，其中 $(x^\prime,y^\prime,z^\prime) \to (x,y,z)$ 表示 $(x^\prime,y^\prime,z^\prime), (x,y,z)$ 之间有边且 $x^\prime + y^\prime + z^\prime \ge x + y + z$。
时间复杂度 $\mathcal O(n^3)$，显然过不了。
考虑如下这样一个博弈问题：
> 有三张 $n$ 个点的有向图，每张图在某个点上都有一个标记。
>
> 有两个人轮流进行移动，每次移动可以将一个标记从一条出边移动过去。
>
> 谁不能移动了谁就输了。
对于这样一个博弈问题，用 $\operatorname{SG}$ 函数可以解决。
然后可以发现，这个博弈问题的 $\operatorname{SG}$ 函数和上面那个 dp 的状态是一样的。
而这个博弈问题中，三张图之间相互独立。
这让我们想到了 $\operatorname{Nim}$ 游戏，即我们可以将三张图的 $\operatorname{SG}$ 函数分开算，最后 $\operatorname{xor}$ 起来得到原来的 $\operatorname{SG}$ 函数。$\operatorname{SG}$ 函数为 $0$ 的点，即为原问题中要选择的点。
注意到，对于一个 DAG 博弈转移图，$\operatorname{SG}$ 函数值的上界是 $\mathcal O(\sqrt n)$ 的，因此我们可以 $\mathcal O(n)$ 求出答案。
```cpp
const int N = 1e5 + 7;
const modint K = 1000000000000000000ll % P;
int n;
modint ans;
struct Graph {
int n, m, sg[N], k;
modint c[N];
vi e[N];
inline Graph() {}
inline Graph(int n) : n(n) {}
int SG(int x) {
if (~sg[x]) return sg[x];
map<int, bool> p;
for (int y : e[x]) p[SG(y)] = 1;
while (p[++sg[x]]);
return sg[x];
}
inline void main() {
rd(m);
for (int i = 1; i <= n; i++) sg[i] = -1;
for (int i = 1, x, y; i <= m; i++) {
rd(x), rd(y);
if (x > y) swap(x, y);
e[x].pb(y);
}
for (int i = 1; i <= n; i++) if (!~sg[i]) SG(i);
for (int i = 1; i <= n; i++) k = max(k, sg[i]), c[sg[i]] += K ^ i;
}
} G[3];
int main() {
rd(n);
for (int i = 0; i < 3; i++) G[i] = Graph(n), G[i].main();
for (int i = 0; i <= G[0].k; i++)
for (int j = 0; j <= G[1].k; j++)
ans += G[0].c[i] * G[1].c[j] * G[2].c[i^j];
print(ans);
return 0;
}
```