题解 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) 求出答案。

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;
}