CF1464E
题意：
Alice 和 Bob 在玩游戏。
在他们面前有一张 \(n\) 个点，\(m\) 条边的有向无环图，每个点初始都是空的，
在游戏开始后，每一秒在图上都会发生如下的操作：
1.在 \([1,n+1]\)范围内等概率选取一个整数 \(v\)。
Alice 和 Bob 轮流操作，Alice 先手。定义玩家的一次操作为将图上的某一顶点的一个芯片根据有向边移到另外一个顶点上。每人每次只能操作一次。如果一个人不能操作，那么他输掉游戏。
现在请你求出 Alice 赢的概率。对998244353 取模。
\(n,m\le 10^5\)
题解：
考虑这个游戏的\(SG\)函数，如果要让最大的\(SG\)函数达到\(x\)，至少需要\(1+2+3+……+x=\frac{x(x+1)}{2}\)条边。
所以这里的\(SG\)函数在\([0,511]\)之间。
设\(f_i\)表示现在的\(SG\)函数异或和为\(i\)，最后\(Alice\)获胜的概率。
设\(cnt_i\)表示\(SG\)值为\(i\)的点的数量。
如果\(i\neq 0\)，那么如果摇到\(n+1\)将直接获胜
否则就只能从其他异或值转移过来
\[f_i=\frac{[i\neq 0]}{n+1}+\sum_{j=0}^{511}\frac{cnt_{i\oplus j}}{n+1}f_j \]这样列出来后，把左边的\(f_i\)挪到右边，把右边的常数项挪到左边，就可以高斯消元了。
最后得到\(f_0\)就是答案。（因为初始状态是\(0\)）
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inv2=499122177,inf=2e18;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<vector<int> > eg(n+1);
vector<int> sg(n+1,-1);
for(int i=1;i<=m;++i)
{
int x,y;cin>>x>>y;
eg[x].emplace_back(y);
}
auto fast=[&](int x,int k) -> int
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%mod;
x=x*x%mod;
k>>=1;
}
return ret;
};
function<void(int)> dfs=[&](int now) -> void
{
if(~sg[now]) return;
vector<bool> vis(520);
for(int t:eg[now])
{
dfs(t);
vis[sg[t]]=1;
}
for(int i=0;;++i)
{
if(!vis[i])
{
sg[now]=i;break;
}
}
};
vector<int> cnt(512);
for(int i=1;i<=n;++i)
{
dfs(i);
++cnt[sg[i]];
}
auto guass=[&](auto &a,int n) -> void
{
for(int i=0;i<n;++i)
{
for(int j=i;j<n;++j)
{
if(a[j][i]!=0)
{
swap(a[i],a[j]);
break;
}
}
int invk=fast(a[i][i],mod-2);
for(int j=0;j<=n;++j) a[i][j]=a[i][j]*invk%mod;
for(int j=0;j<n;++j)
{
if(i!=j&&a[j][i]!=0)
{
int d=a[j][i]%mod;
for(int k=0;k<=n;++k)
{
a[j][k]=(a[j][k]-d*a[i][k]%mod+mod)%mod;
}
}
}
}
};
int w=512;
vector a(w+1,vector<int>(w+1));
int inv=fast(n+1,mod-2);
for(int i=0;i<w;++i)
{
for(int j=0;j<w;++j)
{
a[i][j]=cnt[i^j]*inv%mod;
}
a[i][i]=(a[i][i]-1+mod)%mod;
a[i][w]=i==0?0:(mod-inv);
}
guass(a,w);
int ans=0;
cout<<a[0][w]%mod<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/
还可以另一种思路：
设\(f(x)=\sum_{i=0}^{511}cnt_ix^i\)
我们枚举最后进行了多少轮放置：
假设进行了\(k\)轮放置，那么前\(k\)轮都没有结束游戏，在\(k+1\)轮结束游戏的概率是\((\frac{n}{n+1})^k*\frac{1}{n+1}\)
那么答案幂级数就是
\[g(x)=\sum_{k=0}^\infty (\frac{n}{n+1})^k*\frac{1}{n+1}*(\frac{1}{n}f(x))^k \]这里的\(k\)次方是异或卷积，因为是\(SG\)函数。。
化简一下
\[g(x)=\sum_{k=0}^\infty (\frac{1}{n+1})^{k+1}f(x)^k\\ fwt(g(x))=\sum_{k=0}^\infty (\frac{1}{n+1})^{k+1}fwt(f(x))^k\\ =\frac{1}{n+1}*\frac{1}{1-\frac{1}{n+1}*fwt(f(x))}\\ =\frac{1}{n+1-fwt(f(x))}\\ g(x)=ifwt(\frac{1}{n+1-fwt(f(x))}) \]这时答案是\(1-g(0)\)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
const int N=1e6+10,mod=998244353,inv2=499122177,inf=2e18;
void __init(int n=2000) {}
inline void main()
{
int n,m;
cin>>n>>m;
vector<vector<int> > eg(n+1);
vector<int> sg(n+1,-1);
for(int i=1;i<=m;++i)
{
int x,y;cin>>x>>y;
eg[x].emplace_back(y);
}
auto fast=[&](int x,int k) -> int
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%mod;
x=x*x%mod;
k>>=1;
}
return ret;
};
function<void(int)> dfs=[&](int now) -> void
{
if(~sg[now]) return;
vector<bool> vis(520);
for(int t:eg[now])
{
dfs(t);
vis[sg[t]]=1;
}
for(int i=0;;++i)
{
if(!vis[i])
{
sg[now]=i;break;
}
}
};
vector<int> a(512);
for(int i=1;i<=n;++i)
{
dfs(i);
++a[sg[i]];
}
auto fwt=[&](auto &a,int inv) -> void
{
for(int k=1;2*k<=512;k<<=1)
{
for(int i=0;i<512;i+=2*k)
{
for(int j=0;j<k;++j)
{
int x=a[i+j],y=a[i+j+k];
a[i+j]=inv*(x+y)%mod;
a[i+j+k]=inv*(x-y+mod)%mod;
}
}
}
};
fwt(a,1);
vector<int> b(512);
for(int i=0;i<512;++i)
{
b[i]=fast(n+1-a[i]+mod,mod-2);
}
fwt(b,inv2);
cout<<(1-b[0]+mod)%mod<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
red::__init();
int qwq=1; //cin>>qwq;
while(qwq--) red::main();
return 0;
}
/*
*/