题目描述

有 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

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

发表评论

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

你是机器人吗? =。= *