【博弈】【清华冬令营2018模拟】取石子

写完敢说全网没有这么详细的题解了。
注意：题解长是为了方便理解，所以读起来速度应该很快。

题目描述

有 $n$ 堆石子，第 $i$ 堆有 $x_i$ 个。 $Alice$ 和 $Bob$ 轮流去石子（先后手未定）， $Alice$ 每次从一堆中取走 $a$ 个，$Bob$ 每次从一堆中取走 $b$ 个，无法操作者输。不难发现只会有四种情况：$Alice$ 必胜，$Bob$ 必胜，先手必胜，后手必胜。你需选定若干堆石子（共有 $2^n$ 钟方案），$Alice$ 和 $Bob$ 只能在你选出的堆中取，问四种情况对应的方案数。

输入格式

第一行三个整数 $n,a,b$。
第二行 $n$ 个整数 $x_1,x_2,...,x_n$

输出格式

一行四个整数，分别表示 $Alice$ 必胜，$Bob$ 必胜，先手必胜，后手必胜的方案数，对 $10^9+7$ 取模。

样例

输入样例1

2 2 3
2 3

输出样例1

2 0 1 1

样例解释1

数据范围与提示

对于 $10\%$ 的数据，$n,x_i\le 5$。
对于 $50\%$ 的数据，$n\le 20$。
对于另外 $10\%$ 的数据，$a=b$。
对于又另外 $20\%$ 的数据，$a=1$。
对于 $100\%$ 的数据，$1\le n\le 10^5,1\le a,b,x_i\le 10^9$。

分析

考场没有认真分析，考后知道要分类讨论后就打出来了。
不讲部分分了，因为除了第三条其他的应该也都不会去想。

值得一提的是，当 $a=b$ 时的情况还是有一定启发性的，这告诉我们往奇偶性上面想。

方面处理，我们设 $a<b$。
每堆石子对 $a+b$ 取模，然后可以分四种情况：

1. $x_i<a$，没用，但仅存在这种石堆时后手必胜。

2. $a\le x_i<b$，只要存在即 $a$ 获胜。

3. $b\le x_i<2a$，只和奇偶性有关。

4. $2a\le x_i$，

• 1. 若不存在且 (3) 为奇数个则先手必胜
• 2. 若不存在且 (3) 为偶数个则后手必胜
• 3. 若存在两个及以上则 $a$ 必胜
• 4. 若仅存在一个且 (3) 为奇数个则 $a$ 必胜
• 5. 若仅存在一个且 (3) 为偶数个则先手必胜

1~3 都好理解，4 的 1,2 也好理解；
对于4-3，因为无论如何 $b$ 均无法阻止 $a$ 将局面转化成 (2) 的情况，所以 $a$ 必胜；
对于4-4，相当于在 3 为奇数的情况下多了一个 $2a\le x_i$，注意到此时该堆 $a$ 可多次取石，我们对 $a,b$ 两人分别讨论：

• 对于 $a$ 先手，先取 $2a\le x_i$ 的一堆，之后把这一堆搁在一旁，就变成了 4-1 的情况，即 $b$ 获胜，但最后 $a$ 再取搁在一旁的这堆，此时 $b$ 无法再取，$a$ 获胜。
• 而对于 $b$ 先手，因为对于 $2a\le x_i$ 的一堆，$b$ 仍然最多只能取一次，所以对于 $b$ 而言，场上局面依旧是 4-2（奇数堆 + $2a\le x_i$ 一堆 = 偶数堆），此时后手 $a$ 获胜。

再分析 4-5，类似的，我们堆 $a,b$ 两人分别讨论：

• 对于 $a$ 先手，无论怎么选都能使 $b$ 进入4-2 的必输状态，$a$ 获胜。
• 对于 $b$ 先手，当且仅当其最初选 $2a\le x_i$ 时可使 $a$ 进入 4-2 的必输状态，因为默认玩家很聪明，所以 $b$ 获胜。

思维量很小，于是就可以打了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
const int N=1e5+5,M=1e9+7;
int n,a,b,Bz,x[N],fac[N],inv[N];
inline int Rd(){int s=0,w=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}while (ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();return s*w;}
int qp(int A,int B){
    int res=1;
    while (B){
        if(B&1) res=1ll*res*A%M;
        A=1ll*A*A%M;B>>=1;
    }
    return res;
}
void init(){
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%M;
    inv[n]=qp(fac[n],M-2);
    for(int i=n-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%M;
    return ;
}
int C(int A,int B){
    if(A<B) return 0;
    return 1ll*fac[A]*inv[B]%M*inv[A-B]%M;
}
signed main(){
    // freopen("stone.in","r",stdin);
    // freopen("stone.out","w",stdout);
    n=Rd();a=Rd();b=Rd();
    init();
    for(int i=1;i<=n;i++) x[i]=Rd();
    int c1=0,c2=0,c3=0,c4=0;
    LL ans1=0,ans2=0,ans3=0,ans4=0;
    if(a>b) swap(a,b),Bz=1;
    for(int i=1;i<=n;i++){
        x[i]%=(a+b);
        if(x[i]<a) c1++;
        if(x[i]>=a&&x[i]<b) c2++;
        else if(x[i]>=b&&x[i]<2*a) c3++;
        else if(2*a<=x[i]) c4++;
    }
    // printf("%d %d %d %d\n",c1 ,c2,c3,c4);
    int nw=qp(2,n-c2);
    for(int i=1;i<=c2;i++) (ans1+=1ll*C(c2,i)*nw%M)%=M;  //a<=x[i]<b, A win
    nw=qp(2,n-c2-c4);
    for(int i=2;i<=c4;i++) (ans1+=1ll*C(c4,i)*nw%M)%=M;  //2a<=x[i], at least 2, A win
    ans4=qp(2,c1);
    int C1=qp(2,c1);
    for(int i=0;i<=(c3-1)/2;i++) (ans3+=1ll*C(c3,2*i+1)*C1%M)%=M;//b<=x[i]<2a, c4=0, First win
        // printf("%lld\n",ans3);
    for(int i=1;i<=c3/2;i++) (ans4+=1ll*C(c3,2*i)*C1%M)%=M;      //b<=x[i]<2a, c4=0, Second win
    for(int i=0;i<=c3/2;i++) (ans3+=1ll*c4*C(c3,2*i)%M*C1%M)%=M; //c4=1, c3&1=0, First win
        // printf("%lld\n",ans3);
    for(int i=0;i<=(c3-1)/2;i++) (ans1+=1ll*c4*C(c3,2*i+1)%M*C1%M)%=M;//c4=1,c3&1=1, A win
    if(Bz) swap(ans1,ans2);
    printf("%lld %lld %lld %lld\n",ans1,ans2,ans3,ans4);
    return 0;
}