Written with StackEdit.
T1
取石子（stone）
Description
有(n)堆石子，第(i)堆有(x_i)个。
(Alice)和(Bob)轮流取石子（先后手未定），(Alice)每次从一堆中取走(a)个，(Bob)每次从一堆中取走(b)个，无法操作者输。
不难发现只会有四种情况：(Alice)必胜；(Bob)必胜；先手必胜；后手必胜。
你需要选定若干堆石子（共有(2^n)种方案），(Alice)和(Bob)只能在你选出的堆中取，问以上四种情况对应的方案数。对(10^9+7)取模。
Input
第一行三个整数(n,a,b)，第二行(n)个整数(x_1.....x_n)。
Output
一行四个整数，分别表示(Alice)必胜、(Bob)必胜、先手必胜和后手必胜的方案数，对(10^9+7)取模。
Sample Input
2 2 3
2 3
Sample Output
2 0 1 1
Explanation
选定空集时后手必胜，选定{(2)}时(Alice)必胜，选定{(3)}时先手必胜，选定{(2,3)}时(Alice)必胜。
HINT
对于(10\%)的数据，(n,x_ileq 5)。
对于(50\%)的数据，(nleq 20)。
对于另外(10\%)的数据，(a=b)。
对于又另外(20\%)的数据，(a=1)。
对于(100\%)的数据，(1leq nleq 100000，1leq a,b,x_ileq 10^9)。
Solution
- 假设有(a leq b.)
- 自然可以想到将每堆石子对(a+b)取模.得到一个余数(r).
-
- (r < a),这堆石子谁也不能取.没有影响.随意选即可.
-
- (a leq r<b.)这堆石子只有(Alice)能取,只要选了,(Alice)必胜.
-
- (bleq r <2a.) 这堆石子两人轮流取,取到双方都不能取时,先后手完成了交换.对结果的影响显然只与这样的堆数的奇偶性有关.
-
- (2aleq r <a+b.)这种石子若有(2)堆及以上,无论谁先手,(Alice)总可以从这样的堆中取一次,使其变为情况(2)的一堆,所以(Alice)必胜.若有(1)堆且情况(3)的堆数为偶数,则先手必胜.若有(1)堆且情况(3)的堆数为奇数,则(Alice)必胜.若不存在这种堆,情况(3)为奇数,先手必胜,情况(3)为偶数,后手必胜.
- (Alice)必胜的情况在(2)与(4)中有重叠部分,所以可以计算出先手后手必胜的情况数目,再用总数减去即可.((Bob)不可能必胜).
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int P=1e9+7;
inline int add(int a,int b)
{
return (a+b) % P;
}
inline int mul(int a,int b)
{
return 1LL * a * b % P;
}
inline int sub(int a,int b)
{
return (add(a,-b)+P)%P;
}
int fpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
int flag=0;
int calcodd(int x)
{
if(!x)
return 0;
return fpow(2,x-1);
}
int calceven(int x)
{
if(!x)
return 1;
return fpow(2,x-1);
}
int x[4],ans[4];
int main()
{
int n,a,b;
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
n=read(),a=read(),b=read();
if(a>b)
swap(a,b),flag=1;
for(int i=1; i<=n; ++i)
{
int r=read();
r%=(a+b);
if(r<a)
++x[0];
else if(r>=a && r<b)
++x[1];
else if(r>=b && r<2*a)//这个区间可能为空集.加上else.
++x[2];
else if(r>=2*a)
++x[3];
}
ans[2]=mul(x[3],calceven(x[2]));
ans[2]=add(ans[2],calcodd(x[2]));
ans[2]=mul(ans[2],fpow(2,x[0]));
ans[3]=calceven(x[2]);
ans[3]=mul(ans[3],fpow(2,x[0]));
ans[0]=sub(fpow(2,n),add(ans[2],ans[3]));
if(flag)
swap(ans[0],ans[1]);
for(int i=0; i<4; ++i)
printf("%d ",ans[i]);
return 0;
}
T2
占坑.
T3
占坑.