AGC043C Giant Graph

构造一个 $n^{3}$ 个点的无向图 $G$ ，方法如下：

给定 $3$ 张 $n$ 个点的无向图 $G_{1}, G_{2}, G_{3}$ 。
构造 $n^{3}$ 个点，标号是一个三元组 $⟨ i, j, k ⟩$ 。
对于 $G_{1}$ 中的边 $⟨ u, v ⟩$ ，连边 $⟨ u, j, k ⟩$ 和 $⟨ v, j, k ⟩$ 。
对于 $G_{2}$ 中的边 $⟨ u, v ⟩$ ，连边 $⟨ i, u, k ⟩$ 和 $⟨ i, v, k ⟩$ 。
对于 $G_{3}$ 中的边 $⟨ u, v ⟩$ ，连边 $⟨ i, j, u ⟩$ 和 $⟨ i, j, v ⟩$ 。
对于 $G$ 上的一个点 $⟨ i, j, k ⟩$ ，其点权为 $10^{18 (i + j + k)}$ 。

现在，要你求出 $G$ 的最大独立集大小膜 $998244353$ 以后的值。

$2 \leq n \leq 10^{5}, 1 \leq m_{1}, m_{2}, m_{3} \leq 10^{5}$

考虑到是点权是一个大数的幂次，那肯定是选的数越大越好。

考虑如果你知道了图 $G$ 之后你会怎么做。

首先 $⟨ n, n, n ⟩$ 这个点必须得选，然后其跟她连边的点就不能选了。

然后如果一个点已经确定了旁边已经比她大的点都不选了，那么她才会选。

那会不会有两个相邻的点点权相等呢？显然不会。因为相邻的点必须有两个权值相等，那么另外一个肯定相等，这是不合法的。

然后我们就考虑这个过程，就是我们考虑如何判断一个点选不选，那就要看与之相邻的比她大的点选不选，就是如果那些点都是不合法的，那么这个点合法，否则不合法。

我们发现这跟博弈问题很像，就是有 $3$ 颗棋子，每个人每次可以把一个棋子移动到一个比她大的格子里，不能走的就输了。而先手必输态的点就是合法的。

于是我们只要计算每个点的 sg 值即可。

考虑到每张图 sg 值只会有 $O (\sqrt{n})$ 个，我们只要计算出之后暴力合并即可，于是合并复杂度是 $O (n)$ 的。

cpp

namespace dfcmd {

    typedef long long LL;

    const int maxn = 100005;
    const int mod = 998244353;
    const int di = 1000000000000000000LL % mod;

    int bin[maxn];

    inline void add(int& x, int y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }

    int n;

    struct myhnb {
        int m;
        int sg[maxn];
        int ss[maxn];

        struct Edge {
            int to, nxt;
        } e[maxn];

        int first[maxn];
        int cnt = 0;
        
        inline void add_edge(int u, int v) {
            if (u > v) {
                swap(u, v);
            }
            e[++cnt].nxt = first[u];
            first[u] = cnt;
            e[cnt].to = v;
        }

        int vis[maxn];

        myhnb() {
            memset(first, 0, sizeof(first));
            memset(ss, 0, sizeof(ss));
            memset(vis, 0, sizeof(vis));
        }

        inline void Dfs() {
            for (int now = n; now; --now) {
                vis[now] = true;
                set<int> sgg;
                sgg.clear();
                for (int i = first[now]; i; i = e[i].nxt) {
                    sgg.insert(sg[e[i].to]);
                }
                sg[now] = 0;
                while (sgg.count(sg[now])) {
                    sg[now]++;
                }
                add(ss[sg[now]], bin[now]);
            }
        }

        inline int& operator [] (int x) {
            return ss[x];
        }
    } d[3];

    int main() {
        read(n);
        bin[0] = 1;
        for (int i = 1; i <= n; ++i) {
            bin[i] = (LL) bin[i - 1] * di % mod;
        }
        for (int i = 0; i < 3; ++i) {
            read(d[i].m);
            for (int j = 1; j <= d[i].m; ++j) {
                int u, v;
                read(u), read(v);
                d[i].add_edge(u, v);
            }
            d[i].Dfs();
        }
        int ans = 0;
        for (int i = 0; i <= 1000; ++i) {
            for (int j = 0; j <= 1000; ++j) {
                add(ans, (LL) d[0][i] * d[1][j] % mod * d[2][i ^ j] % mod);
            }
        }
        writeln(ans);
        return 0;
    }
}

Cite this post