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

巴特西

洛谷 P4706 取石子解题报告

P4706 取石子

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

巴特西

洛谷 P4706 取石子 解题报告

P4706 取石子

题目描述

输入输出格式

输入格式：

输出格式：

说明

最新文章

热门文章

洛谷 P4706 取石子解题报告