題目鏈接

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)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。