P4706 取石子

题目描述

现在 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$3 取模。

输入输出格式

输入格式：

第一行一个数 \(n\) 。

第二行 \(n\) 个数 \(a_1, a_2, ..., a_n\) 。

输出格式：

输出 \(m\) 行，表示 Yopilla 能够获胜的概率对 \(998244353\) 取模。

说明

对于 \(20 \%\) 的数据，只有一个石子。

对于 \(100 \%\) 的数据，\(1 \le n \le {10} ^ 6, 0 \le a_i \le {10} ^ 9\)，保证至少有一个不在一号点的石子。

---

太神仙了...

如果把图建出来，我们可以按照每个数的幂的和的奇偶性构造二分图（1为偶），然后就是一个阶梯\(Nim\)问题

link

然后我们筛一下每个数的质因子个数顺便分层，然后统计一下奇层的\(SG\)

总情况很好算

然后枚举一下随机操作对\(SG\)函数的影响

具体的，枚举每一个奇层的点，然后发现这个点要变成\(SG \ xor \ a_i\)才能使对面必败，然后讨论一下这个值是给出去还是由别人给的情况。

最后算一下概率就可以了。

---

Code:

#include <cstdio> const int N=1e6+1; int pri[N],ispri[N],is[N],num[N],cnt; int n,a[N],SG; #define ll long long const ll mod=998244353; ll win,sum; ll qp(ll d,ll k){ll f=1;while(k){if(k&1)f=f*d%mod;d=d*d%mod,k>>=1;}return f;} void init() {for(int i=2;i<=n;i++){if(!ispri[i]){pri[++cnt]=i;num[i]=is[i]=1;}for(int j=1;j<=cnt&&i*pri[j]<=n;j++){int x=i*pri[j];ispri[x]=1;is[x]=is[i]^1;if(i%pri[j]) num[x]=num[i]+1;else {num[x]=num[i];break;}}} } int main() {scanf("%d",&n);init();for(int i=1;i<=n;i++){scanf("%d",a+i);if(is[i]) SG^=a[i];(sum+=1ll*a[i]*num[i])%=mod;}for(int i=1;i<=n;i++)if(is[i]){int to=SG^a[i];if(a[i]>to)(win+=num[i])%=mod;else if(a[i]<to)for(int j=1;j<=cnt&&pri[j]*i<=n;j++)win+=a[i*pri[j]]>=to-a[i];}printf("%lld\n",win*qp(sum,mod-2)%mod);return 0; }

---

2018.12.18

转载于:https://www.cnblogs.com/butterflydew/p/10140080.html

总结

以上是生活随笔为你收集整理的洛谷 P4706 取石子 解题报告的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。