题目描述

有 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 必胜的情况吗？没错，不过发生 “必胜” 事件的话，就可以当做他们就是这么取的，而不用考虑通过别的方式，达到相同的结果。这样一套理论，有点像《命运石之门》中的世界线收束，由于最后会达到同一结果，所以我们可以仅看一条世界线上的结果即可。