洛谷 - Sdchr 的邀请赛 T1 取石子

比赛的时候都推出来了和 质因子的指数和有关，硬是没做出来QWQ，我傻死算了

但其实这是一个结论题，因为这本来就是阶梯NIM游戏的模型。阶梯NIM游戏是指，有 n+1 阶台阶(0 ~ n)，每阶上都有若干堆石子，每次操作从第i(i>0)阶的某一堆拿不超过这一堆数量的石子放到第i-1阶的某一堆中，不能操作者输。

显然普通的nim游戏就是1阶nim，拿到0阶就相当于扔了。、。。。

虽然我也不知道是怎么证的，但是结论就是： 当前游戏是必败态当且仅当 所有奇数阶上的每堆石子的异或和为0.

所以这个题xjb讨论计数一下就好啦QWQ，(我讨厌结论题QWQ)

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=1000000,ha=998244353;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}

inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int ksm(int x,int y){

	int an=1;

	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;

	return an;

}

int zs[maxn/5],num[maxn+5],low[maxn+5];

int t,n,a[maxn+5],ans,pr[maxn+5];

bool v[maxn+5];

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

inline void init(){

	low[1]=1;

	for(int i=2;i<=maxn;i++){

		if(!v[i]) zs[++t]=i,low[i]=pr[i]=i,num[i]=1;

		for(int j=1,u;j<=t&&(u=zs[j]*i)<=maxn;j++){

			v[u]=1,num[u]=num[i]+1,pr[u]=zs[j];

			if(!(i%zs[j])){

			    low[u]=low[i]*zs[j];

				break;

			}

			low[u]=zs[j];

		}

	}

}

inline void solve(){

	int tot=0,can=0,Xor=0;

	for(int i=1;i<=n;i++) if(num[i]&1) Xor^=a[i];

	for(int i=2,now,to;i<=n;i++){

		now=i;

		for(;now!=1;now/=low[now]){

			to=i/pr[now];

			ADD(tot,add(a[i],0));

			if(num[i]&1){

				if((Xor^a[i])<=a[i]) ADD(can,1);

			}

			else{

				if((Xor^a[to])<=a[i]+a[to]&&(Xor^a[to])>=a[to]) ADD(can,1);

			}

		}

	}

	ans=can*(ll)ksm(tot,ha-2)%ha;

}

int main(){

	init();

	while(scanf("%d",&n)==1){

    	for(int i=1;i<=n;i++) a[i]=read();

    	solve();

    	printf("%d\n",ans);

    }

	return 0;

}