[AGC043C] Giant Graph
这题真的抽象。
注意到 \(10^{18} > n^3\)，因此只需按照 \(x+y+z\) 从大到小贪心，由于每次选点只会影响到下面若干层点的可选性，所以可以直接能选就选。时间复杂度 \(O(n^3)\)。
考虑优化，刻画一个点 \((x,y,z)\) 能选中的充要条件，即它的所有前驱都没有被选中。联想到博弈论，令可以选中的点为必败态，那么答案就是所有必败态的权值和。
关于博弈论，我们有什么武器呢？没错——\(\operatorname{SG}\) 函数。注意到三维互不影响，所以这实际上是一个简单组合游戏，可以把单个游戏的 \(\operatorname{SG}\) 函数求出来然后直接取异或和得到整个游戏的 \(\operatorname{SG}\) 函数。这样，我们把式子拆开，就变成了
\[\sum_{\operatorname{SG}_1(x) \oplus \operatorname{SG}_2(y) \oplus \operatorname{SG}_3(z) = 0} 10^{18(x+y+z)}
\]
这个东西是异或卷积的形式可以直接做。当然也可以注意到 \(\operatorname{SG}\) 函数的值域是根号级别然后直接枚举 \(\operatorname{SG}\) 函数值来算。
const LL P = 998244353;
const int N = 1e5 + 10;
const int B = 500;
int n;
int f[B + 10], g[B + 10], h[B + 10];
LL val[N];
void add(int &x, int y) {
(x += y) >= P ? x -= P : 0;
}
vector<int> G[N];
int sg[N], m;
void solve(int *f) {
read(m);
for(int i = 1; i <= n; ++i)
G[i].clear(), sg[i] = 0;
for(int i = 1; i <= m; ++i) {
int u, v; read(u, v);
if(u > v) swap(u, v);
G[u].eb(v);
}
for(int i = n; i >= 1; --i) {
set<int> s;
for(int j : G[i])
s.insert(sg[j]);
for(int j = 0; j <= B; ++j)
if(s.find(j) == s.end()) {
sg[i] = j;
break;
}
add(f[sg[i]], val[i]);
}
}
int main() {
read(n);
val[0] = 1, val[1] = (LL)1e18 % P;
for(int i = 2; i <= n; ++i)
val[i] = val[i - 1] * val[1] % P;
solve(f), solve(g), solve(h);
int ans = 0;
for(int i = 0; i <= B; ++i)
for(int j = 0; j <= B; ++j)
add(ans, 1ll * f[i] * g[j] % P * h[i ^ j] % P);
printf("%d\n",ans);
}