自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:02:48，当前版本为作者最后更新于2021-07-06 12:40:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{Link}$

题意

有 $n$ 堆棋子，第 $i$ 堆有 $a_i$ 个棋子，定义一次操作为选择第 $i$ 堆棋子中任意个棋子转移到第 $j$ 堆中。其中 $j$ 是 $i$ 的质因数。

两人轮流操作，不能操作者输。若先手第一步随机操作一步，问先手获胜的概率。对 $998244353$ 取模。

$1\le n\le 10^6,0\le a_i\le 10^9$。

思路

前置知识：阶梯 $\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]}$，此处不多作介绍，可以参考这份讲解。

设 $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]$ 的贡献。

最后除一下得出概率就行了！

代码：

#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~