题解：AT_agc043_c [AGC043C] Giant Graph

· · 题解

我们注意到 10^{18} 是充分大的，所以对于 a < b，(10^{18})^a 极其小于 (10^{18})^b。

于是，问题可以近似转化为在选择的任意两点无连边的情况下尽量多选 x + y + z 较大的点。

我们可以得到一种暴力的做法：从大到小枚举 x + y + z，再分别确定 x, y, z，如果该点与已选的点没有连边，则选择该点，否则跳过。

我们肯定先选较大的点再选较小的点，所以可以给每一条边定向，使其从后选的较小点连向先选的较大点。这样得到的图显然是 DAG。

一个点在答案中当且仅当其所有出边连向的点都不在答案中，一个点不在答案中当且仅当其存在一条出边使得其连向的点在答案中。

我们发现这很类似 DAG 上一般无环博弈的结构，所有答案里的点都是游戏中的必败态。

考虑如何求出必败态。由于连边每次只能改变 x, y, z 之一，所以可以拆为 3 个图分别讨论。

参考 Nim 游戏，设 \operatorname{sg}(g, u) 表示在图 g 上第 i 个点的 sg 值，则最终图中 u 点为必败态当且仅当 \operatorname{xor}_{i = 1}^{3} \operatorname{sg}(i, u) = 0。

求出 sg 是 \mathcal{O}(n \log n) 的，我们考虑如何快速找出使得 \operatorname{sg}(1, x) \operatorname{xor} \operatorname{sg}(2, y) \operatorname{xor} \operatorname{sg}(3, z) = 0 的 x, y, z。

我们要尝试证明对于一个 m 条边的 DAG，sg 值的上界是 \mathcal{O}(\sqrt{m}) 的。

设某一点的 sg 值为 t，则其至少有 t 个后继且它们的 sg 值分别为 0, 1, \ldots , t - 1。点的数量是无法通过这里确定的，因为一个点可能重复地进行贡献，但边的贡献是不会重复的，从而我们可以确定此处一定有至少 t 条边。归纳可得整张图至少有 \sum_{i = 1}^{t}i = \mathcal{O}(t^2) 条边。所以 m 条边的图 sg 值不可能超过 \mathcal{O}(\sqrt{m})。

从而我们可以直接枚举 \operatorname{sg}(1, x) 和 \operatorname{sg}(2, y)。\operatorname{sg}(3, z) = \operatorname{sg}(1, x) \operatorname{xor} \operatorname{sg}(2, y) 是确定的。时间复杂度 \mathcal{O}(\sqrt{m})^2 = \mathcal{O}(m)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a));

using namespace std;

const int maxn = 1e5 + 10, maxm = 1e5 + 10, maxsqrt = 5e2, mod = 998244353, base = 1000000000000000000ll % mod;

struct{
    int v, nex;
} edge[maxm];

int n, m, res = 0;
long long power[maxn], f[3][maxn];
int sg[maxn];
int head[maxn], top;

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x & x, Tp_y y){
    x += y;
    return x >= mod ? x -= mod : x;
}

inline void add(int u, int v){
    edge[++top].v = v;
    edge[top].nex = head[u];
    head[u] = top;
}

int main(){
    scanf("%d", &n);
    power[0] = 1;
    for (int i = 1; i <= n; i++){
        power[i] = power[i - 1] * base % mod;
    }
    for (int t = 0; t < 3; t++){
        mem(head, 0);
        mem(sg, 0);
        top = 0;
        scanf("%d", &m);
        for (int i = 1; i <= m; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            if (u > v){
                swap(u, v);
            }
            add(u, v);
        }
        for (int u = n; u; u--){
            set<int> mex;
            for (int i = head[u]; i; i = edge[i].nex){
                const int v = edge[i].v;
                mex.insert(sg[v]);
            }
            for (;mex.count(sg[u]); sg[u]++);
        }
        for (int i = 1; i <= n; i++){
            mod_add(f[t][sg[i]], power[i]);
        }
    }
    for (int i = 0; i <= maxsqrt; i++){
        for (int j = 0; j <= maxsqrt; j++){
            mod_add(res, f[0][i] * f[1][j] % mod * f[2][i ^ j] % mod);
        }
    }
    printf("%d", res);

return 0;
}