列表

详情


NC233503. No Game No Life

描述

Alice 和 Bob 在玩游戏。

在他们面前有一张 n 个点,m 条边的有向无环图,每个点有若干芯片,数量为 a_i。Alice 和 Bob 轮流操作,Alice 先手。定义玩家的一次操作为将图上的某一顶点的一个芯片根据有向边移到另外一个顶点上。每人每次只能操作一次。如果一个人不能操作,那么他输掉游戏。

在游戏开始后,每一秒在图上都会发生如下的操作:

1. 在 范围内等概率选取一个整数 v
2. 如果 ,那么在 v 顶点放置一个芯片,这一秒操作结束。
3. 如果 ,那么 Alice 和 Bob 开始游戏,游戏结束后所有操作停止。

保证 Alice 和 Bob 都绝对聪明。

现在请你求出 Alice 赢的概率。对 998244353 取模。

即若概率为最简分数 (保证 ),你只需要输出 x 使得 ,可以证明这样的 x 是唯一的。

输入描述

第一行两个整数 n,m,表示有向无环图的顶点个数与边数。

接下来 m 行,每行两个数 u,v,表示从 uv 有一条有向边。

输出描述

仅一行,表示 Alice 赢的概率。对 998244353 取模。

示例1

输入:

1 0

输出:

0

示例2

输入:

2 1
1 2

输出:

332748118

示例3

输入:

5 5
1 4
5 2
4 3
1 5
5 4

输出:

931694730

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 76ms, 内存消耗: 13632K, 提交时间: 2022-11-18 20:04:14

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e5+10,M = 4e5 + 10,MOD = 998244353;
int h[N],e[M],ne[M],idx;
void add(int a,int b){
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
int n,m,sg[N];
bool vis[N];
int dfs(int u){
	if(vis[u]){
		return sg[u];
	}
	vis[u] = true;
	set<int> st;
	for(int i = h[u];~i;i=ne[i]){
		int j = e[i];
		st.insert(dfs(j));
	}
	for(int i = 0;;++i){
		if(!st.count(i)){
			sg[u] = i;
			return i;
		}
	}
}
int a[N],inv2;
void XOR(int a[],int n,int inv){
	for(int mid = 2,k = 1;mid<=n;mid<<=1,k<<=1){
		for(int i = 0;i<n;i+=mid){
			for(int j = 0;j<k;++j){
				LL t1 = (a[i+j]+a[i+j+k])%MOD;
				LL t2 = (a[i+j]-a[i+j+k])%MOD;
				a[i+j] = (LL)t1*inv%MOD;
				a[i+j+k] = (LL)t2*inv%MOD;
			}
		}
	}
}
int qmi(int a,int b){
	int res = 1;
	a%=MOD;
	while(b){
		if(b&1)res=(LL)res*a%MOD;
		a=(LL)a*a%MOD;
		b>>=1;
	}
	return res;
}
int main() {
//	freopen("a.txt","r",stdin);
	memset(h,-1,sizeof h);
	scanf("%d%d",&n,&m);
	inv2 = qmi(2,MOD-2);
	for(int i = 1;i<=m;++i){
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i = 1;i<=n;++i){
		if(!vis[i])dfs(i);
	}
	int len = 0;
	while((1<<len)<=n)++len;
	for(int i = 1;i<=n;++i){
		a[sg[i]]++;
	}
	XOR(a,1<<len,1);
	for(int i = 0;i<(1<<len);++i){
		a[i] = n+1-a[i];
		a[i] = qmi(a[i],MOD-2);
	}
	XOR(a,1<<len,inv2);
	int ans = 1-a[0];
	ans = (ans%MOD+MOD)%MOD;
	cout<<ans<<'\n';
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 88ms, 内存消耗: 14520K, 提交时间: 2022-08-18 20:47:00

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int mod = 998244353 ;
const int N = 150000 ;
int n,m ;
int A[N],B[N],ind[N],sg[N] ;
bool vis[N] ;
vector<int> g[N],nxt[N] ;
int qsm(int a,int b,int mod)
{
	int ans=1 ;
	while(b)
	{
		if(b&1) ans=(ll)ans*a%mod ;
		a=(ll)a*a%mod ; b>>=1 ;
	}
	return ans ;
}
void polyXOR(int *a,int n,int mul=1)
{
	for(int mid=2,k=1;mid<=n;mid<<=1,k<<=1)
		for(int i=0;i<n;i+=mid)
			for(int j=0;j<k;j++)
			{
				int x=a[i+j],y=a[i+j+k] ;
				a[i+j]=(x+y)%mod ;
				a[i+j+k]=(x-y+mod)%mod ;
				a[i+j]=(ll)a[i+j]*mul%mod ;
				a[i+j+k]=(ll)a[i+j+k]*mul%mod ;
			}
}
int main()
{
	scanf("%d%d",&n,&m) ;
	for(int i=1,u,v;i<=m;++i)
	{
		scanf("%d%d",&u,&v) ;
		g[v].push_back(u) ;
		nxt[u].push_back(v) ;
		ind[u]++ ;
	}
	queue<int>q ;
	for(int i=1;i<=n;++i) if(!ind[i])
	{
		q.push(i) ; sg[i]=0 ;
	}
	int maxsg=0 ;
	while(!q.empty())
	{
		int x=q.front() ; q.pop() ;
		for(auto &y:nxt[x]) vis[sg[y]]=1 ;
		sg[x]=0 ; while(vis[sg[x]]) sg[x]++ ;
		for(auto &y:nxt[x]) vis[sg[y]]=0 ;
		for(auto &y:g[x]) if(!--ind[y]) q.push(y) ;
		maxsg=max(maxsg,sg[x]) ;
	}
	for(int i=1;i<=n;++i) A[sg[i]]++ ;
	int l=1,t=1 ;
	while(l<=maxsg) l<<=1,t++ ;
	polyXOR(A,l) ;
	for(int i=0;i<l;++i) A[i]=qsm(n+1-A[i],mod-2,mod) ;
	polyXOR(A,l,qsm(2,mod-2,mod)) ;
	printf("%d\n",(1-A[0]+mod)%mod) ;
	return 0 ;
}

上一题