kmjp's blog

競技プログラミング参加記です

Codeforces #692 Div1 E. No Game No Life

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;
}
||

*まとめ