Codeforces 题面传送门 & 洛谷题面传送门

一道肥肠套路的题目。

首先这题涉及博弈论。注意到这里每一个棋子的移动方式都是独立的，因此可以考虑 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;
}