题目
正解
直接说做法了，挺好理解的。
钦定(ale b)。
设(r=xmod (a+b))。
分四种情况讨论：
- (rin [0,a-1])。这个情况没有意义。
- (rin [a,b-1])。这个情况下，(A)能多走一步而(B)不能，所以只要出现了这个情况(A)必胜。
- (rin [b,2a-1])。这个情况下，两个人都能各走一步。所以这个情况相当于改变先后手顺序。
- (rin [2a,a+b-1])。这个情况下，(A)能多走至少(2)步，(B)能多走至少(1)步。如果(B)先手，相当于有个情况(3)；如果(A)先手，(A)必胜。如果这个情况出现了两次，那么(A)无论先手后手都必胜。
可能(b)和(2a)的大小关系会有问题，但是没有太大关系。（按照代码中的那样分类就是了）
答案先乘上(2^{cnt1})。
计算先手必胜和后手必胜的方案：
先手必胜：(sum_{imod 2=1} inom{cnt3}{i}+sum_{imod 2=0}inom{cnt3}{i}cnt4)
后手必胜：(sum_{imod 2=0} inom{cnt3}{i})（这里没有(cnt4)的原因是如果有(A)必胜）
代码
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define mo 1000000007
#define ll long long
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
ll fac[N],ifac[N];
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
void initC(int n){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n]);
for (int i=n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
}
int n,a,b;
int x[N];
ll ansA,ansB,ansF,ansS;
void work(){
initC(n);
ll cnt1=0,cnt2=0,cnt3=0,cnt4=0;
for (int i=1;i<=n;++i){
int r=x[i]%(a+b);
if (r<a)
cnt1++;
else if (r<b)
cnt2++;
else if (r<a*2)
cnt3++;
else
cnt4++;
}
for (int i=0;i<=cnt3;++i)
if (i&1)
(ansF+=C(cnt3,i))%=mo;
else{
(ansS+=C(cnt3,i))%=mo;
(ansF+=C(cnt3,i)*cnt4)%=mo;
}
ll tmp=qpow(2,cnt1);
(ansF*=tmp)%=mo;
(ansS*=tmp)%=mo;
ansA=(qpow(2,n)-ansF-ansS+mo+mo)%mo;
}
int main(){
// freopen("in.txt","r",stdin);
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
scanf("%d%d%d",&n,&a,&b);
for (int i=1;i<=n;++i)
scanf("%d",&x[i]);
if (a>b){
swap(a,b);
work();
swap(ansA,ansB);
}
else
work();
printf("%lld %lld %lld %lld
",ansA,ansB,ansF,ansS);
return 0;
}