很显然111就是这个游戏的终止位置,而每个石头走到111的步数是确定的。
很显然这是一个阶梯博弈,一个位置的奇偶性就是所有质因子的指数之和的奇偶性。
显然总的合法操作个数就是∑i=1naibi\sum_{i=1}^{n}a_ib_i∑i=1naibi,其中bib_ibi表示iii的不同质因子个数。
那么现在考虑每个奇位置把石头挪开或者从偶位置挪过来。
假设iii是一个奇位置,所有奇位置的异或和为XorXorXor,我们现在需要把iii上的数变成Xor⊕aiXor\oplusa_iXor⊕ai才能使得下一个局面先手必败,设need=Xor⊕aineed=Xor\oplusa_ineed=Xor⊕ai。
如果need=aineed=a_ineed=ai,显然我们不能动,怎么动下一个局面都是先手必胜。
如果need<aineed<a_ineed<ai,显然只需要把iii位置上多的转移到下方的偶位置就行了,方案数为bib_ibi。
如果need>aineed>a_ineed>ai,枚举所有能够直接转移到iii的偶位置,看这个位置上有没有足够的石头来把aia_iai加到needneedneed就行了。
代码:
#include<bits/stdc++.h>#definelllonglong#definereregister#definegcget_char#definecsconstnamespaceIO{inlinecharget_char(){staticcsintRlen=1<<22|1;staticcharbuf[Rlen],*p1,*p2;return(p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;}template<typenameT>inlineTget(){charc;while(!isdigit(c=gc()));Tnum=c^48;while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);returnnum;}inlineintgetint(){returnget<int>();}}usingnamespaceIO;usingstd::cerr;usingstd::cout;csintmod=998244353;inlineintadd(inta,intb){return(a+=b)>=mod?a-mod:a;}inlineintdec(inta,intb){return(a-=b)<0?a+mod:a;}inlineintmul(inta,intb){llr=(ll)a*b;returnr>=mod?r%mod:r;}inlineintpower(inta,intb,intres=1){for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));returnres;}inlinevoidInc(int&a,intb){(a+=b)>=mod&&(a-=mod);}inlinevoidDec(int&a,intb){(a-=b)<0&&(a+=mod);}csintN=1e6+7;intb[N],c[N];boolmark[N];intprime[N],pcnt;inlinevoidlinear_sieves(intlen){for(intrei=2;i<=len;++i){if(!mark[i])prime[++pcnt]=i,b[i]=c[i]=1;for(intrej=1;i*prime[j]<=len;++j){mark[i*prime[j]]=true;c[i*prime[j]]=c[i]^1;if(i%prime[j])b[i*prime[j]]=b[i]+1;else{b[i*prime[j]]=b[i];break;}}}}intn,a[N];intXor,all,ok;signedmain(){#ifdefzxyoifreopen("stone.in","r",stdin);#endifn=getint();linear_sieves(n);for(intrei=1;i<=n;++i){a[i]=getint();if(c[i])Xor^=a[i];Inc(all,mul(a[i],b[i]));}for(intrei=1;i<=n;++i){if(c[i]){intneed=Xor^a[i];if(need==a[i])continue;if(need<a[i])Inc(ok,b[i]);else{need-=a[i];for(intrej=1;j<=pcnt&&i*prime[j]<=n;++j)if(a[i*prime[j]]>=need)Inc(ok,1);}}}cout<<power(all,mod-2,ok)<<"\n";return0;}