AtCoder AGC043C Giant Graph (图论、SG函数、FWT)

题目链接

https://atcoder.jp/contests/agc043/tasks/agc043_c

题解

场上感觉没啥思路就放弃了，场下想了十几分钟发现是水题，血亏。。。（只能怪自己计数水平太屑做不出 D）
首先显然是按 \((i+j+k)\) 从大到小贪心，考虑图只有一维的情况，我们给无向边定向，从标号小的点连向标号大的点，设 \(u\) 点的出点集合为 \(adj[u]\), \(f[u]\) 表示 \(u\) 点是否能选，则 \(f[u]=\neg \or_{v\in adj[u]} f[v]\).
仔细观察这个式子，能想到什么？SG 函数！这个 \(f[u]\) 还有另外一层意义：在图上的 \(u\) 点有一枚棋子，先后手轮流操作，每次将棋子沿一条出边移动出去，不能移动的输，则 \(f[u]\) 为 \(1\) 代表该点先手必败，为 \(0\) 代表该点先手必胜。
于是对于三维（甚至更高维）的情况做法也清楚了：多维就相当于多个游戏的叠加，于是使用 SG 函数解决，答案等于 \(\sum_{sg[u_1]\oplus sg[u_2]\oplus sg[u_3]=0} (10^{18})^{u_1+u_2+u_3}\), 也即对三个序列进行异或卷积，最后的答案就是所得序列中 \(0\) 处的值。
时间复杂度 \(O(n\log n)\).

代码

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 1<<17; const int P = 998244353; const llong Inv2 = 499122177ll; const llong W = 716070898ll; int sg[mxN+3]; llong pwW[mxN+3]; llong f[3][mxN+3],g[mxN+3]; vector<int> adj[mxN+3]; vector<int> vec; int n,m,dgr;int get_mex() {int ret = 0; sort(vec.begin(),vec.end());for(int i=0; i<vec.size(); i++){if(vec[i]==ret) {ret++;}else if(vec[i]>ret) {break;}}vec.clear(); return ret; }void fwt(int dgr,int coe,llong poly[],llong ret[]) {for(int i=0; i<(1<<dgr); i++) ret[i] = poly[i];for(int i=1; i<(1<<dgr); i<<=1){for(int j=0; j<(1<<dgr); j+=(i<<1)){for(int k=0; k<i; k++){llong x = ret[j+k],y = ret[j+i+k];ret[j+k] = (x+y)%P,ret[j+i+k] = (x-y+P)%P;if(coe==-1) {ret[j+k] = ret[j+k]*Inv2%P,ret[j+i+k] = ret[j+i+k]*Inv2%P;}}}} }int main() {scanf("%d",&n); while((1<<dgr)<=n) dgr++;pwW[0] = 1ll; for(int i=1; i<=n; i++) pwW[i] = pwW[i-1]*W%P;for(int T=0; T<3; T++){scanf("%d",&m);for(int i=1; i<=m; i++){int u,v; scanf("%d%d",&u,&v);if(u>v) {swap(u,v);} adj[u].push_back(v);}for(int i=n; i>=1; i--){for(int o=0; o<adj[i].size(); o++){vec.push_back(sg[adj[i][o]]);}sg[i] = get_mex(); // printf("sg[%d]=%d\n",i,sg[i]);f[T][sg[i]] = (f[T][sg[i]]+pwW[i])%P;}for(int i=1; i<=n; i++) adj[i].clear(),sg[i] = 0;fwt(dgr,1,f[T],f[T]);}for(int i=0; i<(1<<dgr); i++) {g[i] = f[0][i]*f[1][i]%P*f[2][i]%P;}fwt(dgr,-1,g,g);printf("%lld\n",g[0]);return 0; }

总结

以上是生活随笔为你收集整理的AtCoder AGC043C Giant Graph (图论、SG函数、FWT)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。