题目描述

有 n 堆石子, 第 i 堆有 xi 个。

Alice 和 Bob 轮流取石子 (先后手未定), Alice 每次从一堆中取走 a 个, Bob 每次从一堆中取走 b 个, 无法操作者输。

不难发现只会有四种情况:Alice 必胜;Bob 必胜; 先手必胜; 后手必胜。

现在有 n 堆石子,第 i 堆有 $x_i$个。你需要选定若干堆石子 (共有 $2^n$ 种方案),Alice 和 Bob 只能在你选出的堆中取, 问以上四种情况对应的方案数,对 1e9+7 取模。

数据范围

$1 \leq n \leq 10^5,1 \leq a,b,x_i \leq 10^9$

解题思路

对于每 a+b 个石子,一定是 Alice 取一次,Bob 取一次,不论先后手。所以,我们暂且都不看这些 a+b,也就是,将所有 $x_i$都模一个 $a+b$(其实这么说不严谨,可以看一看补充部分,这是大佬 psb 关于取模正确性的讲解)

假设 $a < b$,然后一共有四种情况

0.$x_i < a$,这种石堆只剩下 “零头” 后,Alice 也不能取,Bob 也不能取,所以是没有用的,有没有这种石堆无所谓。

1.$a \leq x_i < b$,假设存在这种石堆,假如不算这个 “零头”,Alice 没有石子取了,她就可以取这些石子,而 Bob 取不了,Alice 获胜。而如果是 Bob 没有石子取了,Bob 还是取不了这些石子,所以还是 Alice 赢。故,只要存在这种石堆,就是 Alice 必胜。

2.$b \leq x_i < 2a$,这种是无论 Alice 还是 Bob 都只能再取一次,要和下面的一起看。

3.$2a \leq x_i < a+b$

假如存在两个及以上的这种石堆,那么对于这些石子,也是 Alice 一次 Bob 一次,每次都是取不同的一堆,那么到最后 Bob 一定没有石子取了,而有些石堆还剩下至少 a 个石子,Alice 还可以取,所以 Alice 必胜。

假如存在一个这种石堆,那么这个石堆的零头可供 Alice 取两次,Bob 取一次,且 Bob 取了之后 Alice 就不能取。若 (2) 石堆有偶数个,那么按照先手,后手,先手,如此顺序取掉(2),最后一定是先手来取(3),所以先手必胜。坑人的是,若(2)为奇数个,并不是后手胜了:因为若只剩下 (2)(3) 的零头时,轮到 Alice 取了,她会取(3)石堆,然后按照 Bob,Alice,Bob… 的顺序,取完(2)后一定是又轮到 Alice 取,她还可以取(3)石堆。而若轮到 Bob 取了,对于 Bob 而言,目前所有石堆他都只能取一次,Alice 也可以把所有石堆视作只能取一次,那么就是有偶数个石堆,会导致先手,也就是 Bob 输掉。综上,此种情况下 Alice 必胜。

假如不存在这种石堆,易证,奇数个(2)则先手必胜,偶数个则后手必胜。

用组合数学基本知识推一推公式即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
int bg,sm,n,s[2],Pw[2],Fw,Sw,js[4],bin[100005];
int qm(int x) {return x>=mod?x-mod:x;}
int main()
{
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    scanf("%d%d%d",&n,&s[0],&s[1]);
    bg=(s[1]>s[0]),sm=bg^1;
    for(int i=1;i<=n;++i) {
        int x;scanf("%d",&x),x%=s[0]+s[1];
        if(x<s[sm]) ++js[0];
        else if(x<s[bg]) ++js[1];
        else if(x<2*s[sm]) ++js[2];
        else ++js[3];
    }
    bin[0]=1;for(int i=1;i<=n;++i) bin[i]=qm(bin[i-1]+bin[i-1]);
    Pw[sm]=1LL*(bin[js[1]]-1+mod)*bin[n-js[1]]%mod;
    Pw[sm]=qm(Pw[sm]+1LL*(bin[js[3]]-(js[3]+1)%mod+mod)*bin[js[0]+js[2]]%mod);
    Pw[sm]=qm(Pw[sm]+1LL*js[3]*bin[js[0]]%mod*1LL*(js[2]?bin[js[2]-1]:0)%mod);
    Fw=1LL*js[3]*(js[2]?bin[js[2]-1]:1)%mod*1LL*bin[js[0]]%mod;
    Fw=qm(Fw+1LL*(js[2]?bin[js[2]-1]:0)*bin[js[0]]%mod);
    Sw=1LL*(js[2]?bin[js[2]-1]:1)*bin[js[0]]%mod;
    printf("%d %d %d %d\n",Pw[0],Pw[1],Fw,Sw);
    return 0;
}

补充

为什么要取模呢?

比如说,假如 A 不停地取第一堆,B 不停的取第二堆呢?

如果这样子 A 可以获胜,那么 B 就会想要破坏这种局面,就会去取第一堆。如果这样 B 可以获胜,那么 A 就不会这么干了。

当然,你会说,两人轮流取同一堆不也会有 A 和 B 必胜的情况吗?没错,不过发生 “必胜” 事件的话,就可以当做他们就是这么取的,而不用考虑通过别的方式,达到相同的结果。这样一套理论,有点像《命运石之门》中的世界线收束,由于最后会达到同一结果,所以我们可以仅看一条世界线上的结果即可。

分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

2 条评论

nosta · 2018年12月23日 6:14 下午

公式好像崩了呀

    litble · 2018年12月23日 6:26 下午

    你需要换个浏览器

发表评论

电子邮件地址不会被公开。 必填项已用*标注