题解 P4706【取石子】
cyffff
·
·
题解
\text{Link}
题意
有 n 堆棋子，第 i 堆有 a_i 个棋子，定义一次操作为选择第 i 堆棋子中任意个棋子转移到第 j 堆中。其中 j 是 i 的质因数。
两人轮流操作，不能操作者输。若先手第一步随机操作一步，问先手获胜的概率。对 998244353 取模。
## 思路
前置知识：阶梯 $\text{Nim}$ 博弈
描述：有 $n$ 堆棋子，第 $i$ 堆有 $a_i$ 个棋子，定义一次操作为选择第 $i$ 堆棋子中任意个棋子转移到第 $i-1$ 堆中。两人轮流操作，不能操作者输。求先手是否有必胜策略。
可以得到，此时的 $\text{SG}$ 函数 $f(x)=a_1\text{ xor }a_3\text{ xor }a_5\text{ xor }\cdots\text{ xor } a_{n-[2|n]}$，此处不多作介绍，可以参考[这份讲解](https://www.cnblogs.com/RogerDTZ/p/9439540.html)。
****
设 $x$ 的标准分解式为 $\prod_{i=1}^k p_i^{q_i}$，定义 $s_x=k,c_x=\sum_{i=1}^kq_i$。这个可以线性筛出来。
我们发现，如果以 $c_i$ 的奇偶性分层连边，则问题转化为在奇偶层之间移动棋子的阶梯 $\text{Nim}$ 博弈。
首先我们知道先手第一步走的方式有 $\sum_{i=1}^n s_ia_i$ 种。
然后来判断有多少种合法方法。
枚举奇层的所有 $i$，若操作后 $f(x)$ 变为 $0$，则先手能胜利，则定义 $need=f(x)\text{ xor } a_i$，则 $a_i$ 变为 $need$ 后 $f(x)$ 变为 $0$。
然后对于 $need$ 和 $a_i$ 的大小分类讨论。
- $need=a_i$，此时 $f(x)=0$，若对 $a_i$ 做出改动，则 $f(x)$ 定不等于 $0$，故此类无贡献；
- $need<a_i$，考虑将 $i$ 处的 $a_i-need$ 颗棋子转移至偶层，则对答案作出 $s_i$ 的贡献；
- $need>a_i$，考虑枚举 $ip=j$，将偶层 $j$ 处的 $need-a_i$ 颗棋子转移至奇层 $i$ 处，则对答案作出 $\sum_{j=ip}[a_j\ge need-a_i]$ 的贡献。
最后除一下得出概率就行了！
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
}
const int N=1e6+10,mod=998244353;
int n,a[N],rnd,sol;
bitset<N>p;
int pri[N],cnt,sum[N];
bool odd[N];
/*
sum->质因数个数
odd->指数和是否为奇
*/
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
inline void sieve(int n){
p[1]=1;
for(int i=2;i<=n;i++){
if(!p[i]){
pri[++cnt]=i;
sum[i]=odd[i]=1;
}
for(int j=1;j<=cnt&&i*pri[j]<=n;j++){
p[i*pri[j]]=1;
odd[i*pri[j]]=odd[i]^1;
if(i%pri[j]==0) { sum[i*pri[j]]=sum[i]; break; }
sum[i*pri[j]]=sum[i]+1;
}
}
}
int SG;
int main(){
n=read();
sieve(n);
for(int i=1;i<=n;i++){
a[i]=read();
if(odd[i]) SG^=a[i];
rnd=(rnd+1ll*a[i]*sum[i])%mod;
}
for(int i=1;i<=n;i++){
if(odd[i]){
int need=SG^a[i];
if(need==a[i]) continue;
if(need<a[i]) sol=(sol+sum[i])%mod;
else{
for(int j=1;j<=cnt&&pri[j]*i<=n;j++){
if(a[i*pri[j]]>=need-a[i]) sol++;
}
sol-=sol>=mod?mod:0;
}
}
}
write(1ll*sol*qpow(rnd,mod-2)%mod);
flush();
}
```
再见 qwq~