Description

　　

​　　 现在 Yopilla 和 yww 要开始玩游戏！

　　

　　​ 他们在一条直线上标记了 \(n\) 个点，从左往右依次标号为 \(1, 2, ..., n\) 。然后在每个点上放置一些棋子，其中第 \(i\) 个点放置了 \(a_i\) 个棋子。接下来，从 Yopilla 开始操作，双方轮流操作，谁不能操作谁输。每次的操作是：当前操作方选定一个有棋子的点 \(x\) ，然后选择至少一个点 \(x\) 上的棋子，然后把这些棋子全都移动到点 \(x / prime\) 上，其中 \(prime\) 是一个质数，且 \(prime \mid x\)

　　

　　​ Yopilla 最初一次操作的策略是随机的：随机找到一个有棋子的点 \(x\) ，随机选择正整数个棋子 \(y\) ，随机转移到一个能转移到的点 \(z\) 。所有棋子可以看作是一样的，换句话说：两种操作不同，当且仅当三元组 \((x, y, z)\) 不同。之后双方都按照最优策略来操作。

　　

​　　 Yopilla 想要预测，他能够获胜的概率是多少，答案对 \(998244353\) 取模。

　　

​　　

　　

　　

　　

Solution

　　

​　　 我们发现，对于每一个数，如果以其幂指数之和为下标来将它们重新排列成一个数组，这个问题就变成了。一次操作，相当于将一个数移动到其左边。不能移动者输。

　　

​　　 事实上我们不需要实现这个重排操作。我们只需要知道每个数重排后是否在奇位置即可。

　　

​　　 记输入数列为\(a\)，我们统计出所有处于奇位置的数\(x\)的\(a_x\)的异或和\(sum\)。

　　

​　　 我们要统计Yopilla一开始的随机操作一共有多少种可能、以及总共有多少种可能，使得操作后局面的先手必败。前者很好计算，就是\(\sum_x a_x*b_x\)，其中\(b_x\)表示\(x\)这个数的不同质因子个数。

　　

​　　 后者如何计算呢？对操作分类：（1）移动奇位置的数至偶位置、（2）移动偶位置的数至奇位置。

　　

​　　 我们枚举所有奇位置的数。假设对该位置\(i\)操作后，总异或和\(sum\)等于0，即操作后先手必败，则\(a_i\)应该由\(a_i\)变成\(target=sum\; \text{xor}\; a_i\)，

　　

　　如果原值比目标值大，那么显然（1）容易满足，选出\(a_i-target\)个数，并将它们通过任意一个质因子移动到偶位置，一共有\(b_i\)种合法情况。

　　

　　如果原值与目标值相等，则什么也做不了，一改就不满足要求，不作为合法情况考虑。

　　

　　若原值小于目标值，则考虑（2），枚举所有能转移到\(i\)的偶位置\(j=i*p\)（其中\(p\)是枚举的质数），如果\(a_j \ge target-a_i\)，那么合法情况就多了一种，因为\(j\)可以选\(target-a_i\)个数通过唯一一种方式——除去\(p\)——来到达\(i\)。

　　

​　　 那么概率也就很好计算了。

　　

　　

　　

Code

　　

#include 
    
     using namespace std;const int N=1000005,MOD=998244353;int n,a[N];bool vis[N];int p[N],pcnt,b[N],c[N];void sieve(){    int up=1e6;    for(int i=2;i<=up;i++){        if(!vis[i]){            p[++pcnt]=i;            b[i]=c[i]=1;        }        for(int j=1;j<=pcnt&&i*p[j]<=up;j++){            int x=i*p[j];            vis[x]=true;            c[x]=c[i]^1;            if(i%p[j]==0){                b[x]=b[i];                break;            }            b[x]=b[i]+1;        }    }}void readData(){    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%d",a+i);}inline int fmi(int x,int y){    int res=1;    for(;y;x=1LL*x*x%MOD,y>>=1)        if(y&1) res=1LL*res*x%MOD;    return res;}void solve(){    int x=0;    for(int i=1;i<=n;i++)         if(c[i]) x^=a[i];    int legal=0;    for(int i=1;i<=n;i++)        if(c[i]){            int best=x^a[i];            if(best
     
      =delta) legal++;            }        }    int all=0;    for(int i=1;i<=n;i++)         (all+=1LL*a[i]*b[i]%MOD)%=MOD;    int ans=1LL*legal*fmi(all,MOD-2)%MOD;    printf("%d\n",ans<0?ans+MOD:ans);}int main(){    sieve();    readData();    solve();    return 0;}
     
    

​

​