DよりEの方がだいぶ難易度低い。
https://codeforces.com/contest/1464/problem/E
問題
DAGを成すN点M辺のグラフが与えられる。
ここで2人ターン制のゲームを行う。
グラフの各点には、コインが何枚か置かれているものとする。
自分のターンでは、1枚コインを選び辺に沿って移動させる。
もし移動できるコインがなければ負けとなる。
コインの置き方は以下のように決まる。
- 1~(N+1)のいずれかの値を等確率に1つ選ぶ
- 選んだ値がN以下なら、対応する頂点にコインを1枚追加する
- 選んだ値がN+1なら、今の状態でゲームを開始する
このゲームで、両者最適手を打つとき、先手の勝率はいくつか。
解法
まず各点に対応するGrundy数を求めよう。
この時Grundy数の最大値は高々O(√M)である。
コインを1枚置くと、その頂点のGrundy数に対応する分だけ、そのxorの値が変化する。
xorの値vが決まれば、その時の勝率P(v)が決まる。コインが1枚もない状態、P(0)が求める解となる。
コインを各頂点に置く確率から、xorがどの値からどの値に変化するか、その確率わかるので、その状態遷移を掃き出し法にかければP(0)がわかる。
int N,M; vector<int> E[101010],RE[101010]; int in[101010]; int gr[101010]; int cgr[101010]; const ll mo=998244353; const int MAT=512; ll ma[MAT][MAT],V[MAT],R[MAT]; ll rev(ll a, ll n = mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } int Gauss(int n,ll mat_[MAT][MAT],ll v_[MAT],ll r[MAT]) { int i,j,k; ll mat[MAT][MAT],v[MAT]; memmove(mat,mat_,sizeof(mat)); memmove(v,v_,sizeof(v)); FOR(i,n) { if(mat[i][i]==0) { for(j=i+1;j<n;j++) if(mat[j][i]) break; if(j>=n) return i; FOR(k,n) swap(mat[i][k],mat[j][k]); swap(v[i],v[j]); } (v[i]*=rev(mat[i][i]))%=mo; for(k=n-1;k>=i;k--) (mat[i][k]*=rev(mat[i][i]))%=mo; for(j=i+1;j<n;j++) { v[j]=((v[j]-v[i]*mat[j][i]%mo)+mo)%mo; for(k=n-1;k>=i;k--) mat[j][k]=((mat[j][k]-mat[i][k]*mat[j][i]%mo)+mo)%mo; } } for(i=n-1;i>=0;i--) { for(j=n-1;j>i;j--) v[i]=((v[i]-mat[i][j]*v[j]%mo)+mo)%mo; r[i]=v[i]; } return n; } ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; x--,y--; E[x].push_back(y); RE[y].push_back(x); in[x]++; } queue<int> Q; FOR(i,N) if(in[i]==0) Q.push(i); int num=1; while(Q.size()) { x=Q.front(); Q.pop(); FORR(e,RE[x]) { in[e]--; if(in[e]==0) Q.push(e); } set<int> S; FORR(e,E[x]) S.insert(gr[e]); while(S.count(gr[x])) gr[x]++; if(gr[x]) num++; cgr[gr[x]]++; assert(gr[x]<=512); } V[0]=modpow(num); FOR(i,MAT) { ma[i][i]=1; for(j=1;j<MAT;j++) if(cgr[j]) ma[i^j][i]=mo-cgr[j]*modpow(num)%mo; } Gauss(MAT,ma,V,R); cout<<(1+mo-R[0])%mo<<endl; } || *まとめ