Codeforces 1411G - No Game No Life（博弈论+生成函数+FWTxor）

一道肥肠套路的题目。

首先这题涉及博弈论。注意到这里每一个棋子的移动方式都是独立的，因此可以考虑 SG 定理。具体来说，我们先求出每个棋子放在每个位置的 SG 函数——这个是非常好求的，具体方法就是建反图拓扑排序，求集合的 MEX 时可以 map 存，也可以直接枚举，复杂度 \(m\sqrt{m}\) 或 \(m\sqrt{m}\log m\)（反正我使用的 map 没有 TLE 就是了）

于是问题转化为，有多大概率满足开始游戏时，所有棋子放置位置的 SG 值的异或和不为 \(0\)。注意到这里涉及异或和及无穷级数，因此考虑生成函数，我们考虑集合幂级数 \(A\)，其中 \([x^n]A\) 表示一次随机放置的点的 SG 值等于 \(n\) 的概率，那么不难发现答案即为 \(1-\dfrac{1}{n+1}[x^0]\sum\limits_{k\ge 0}A^k\)。显然这东西可以化简为 \(1-\dfrac{1}{n+1}[x^0]\dfrac{1}{1-A}\)，然后用 FWTxor 的套路随便搞一下即可。

时间复杂度 \(m\sqrt{m}\)（当然我的程序是 \(m\sqrt{m}\log m\)，不过跑得飞快）

const int MAXN=1e5;

const int MAXP=1<<17;

const int MOD=998244353;

const int INV2=499122177;

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,m,deg[MAXN+5],hd[MAXN+5],to[MAXN+5],nxt[MAXN+5],ec=0;

void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}

map<int,int> vis[MAXN+5];int sg[MAXN+5],a[MAXP+5];

void FWTxor(int *a,int len,int type){

	for(int i=2;i<=len;i<<=1)

		for(int j=0;j<len;j+=i)

			for(int k=0;k<(i>>1);k++){

				int X=a[j+k],Y=a[(i>>1)+j+k];

				a[j+k]=1ll*type*(X+Y)%MOD;

				a[(i>>1)+j+k]=1ll*type*(X-Y+MOD)%MOD;

			}

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),deg[u]++,adde(v,u);

	queue<int> q;

	for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);

	while(!q.empty()){

		int x=q.front();q.pop();

		while(vis[x][sg[x]]) ++sg[x];

		for(int e=hd[x];e;e=nxt[e]){

			int y=to[e];vis[y][sg[x]]=1;

			if(!--deg[y]) q.push(y);

		}

	} int ivn=qpow(n+1,MOD-2);

	for(int i=1;i<=n;i++) a[sg[i]]++;

	for(int i=0;i<n;i++) a[i]=1ll*a[i]*ivn%MOD;

	FWTxor(a,MAXP,1);

	for(int i=0;i<MAXP;i++) a[i]=qpow((1-a[i]+MOD)%MOD,MOD-2);

	FWTxor(a,MAXP,INV2);

	printf("%d\n",(1-1ll*a[0]*ivn%MOD+MOD)%MOD);

	return 0;

}

巴特西

Codeforces 1411G - No Game No Life（博弈论+生成函数+FWTxor）

最新文章

热门文章