xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 AT5800 【[AGC043C] Giant Graph】

以下设 $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;
}

2020-03-22 18:18:23 in 题解