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
我们发现，对于每一个数，如果以其幂指数之和为下标来将它们重新排列成一个数组，这个问题就变成了阶梯(Nim)问题。一次操作，相当于将一个数移动到其左边。不能移动者输。
事实上我们不需要实现这个重排操作。我们只需要知道每个数重排后是否在奇位置即可。
记输入数列为(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; ext{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 <cstdio>
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<a[i]) legal+=b[i];
else{
int delta=best-a[i];
if(!delta) continue;
for(int j=1;j<=pcnt&&i*p[j]<=n;j++)
if(a[i*p[j]]>=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
",ans<0?ans+MOD:ans);
}
int main(){
sieve();
readData();
solve();
return 0;
}