NC233503. No Game No Life
描述
输入描述
第一行两个整数,表示有向无环图的顶点个数与边数。
接下来行,每行两个数
,表示从
到
有一条有向边。
。
输出描述
仅一行,表示 Alice 赢的概率。对取模。
示例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 ; }