题目链接:
题意：有m张扑克牌，可以进行n次操作，每次操作翻转Xi张牌，即把0->1或者1->0，问最终这m张扑克牌会呈现出多少种不同的翻转情况。
题解：
#include<cstdio>
const int maxn = 100010;
const int mod = 1000000009;
typedef long long int;
int f[maxn];
int pow_mod(int a, int b)
{
int ans = 1;
for(; b ; b>>=1, a = a * a % mod)
{
if(b & 1)
ans = ans * a % mod;
}
return ans % mod;
}
int C(int n, int r)
{
if(n - r < r) r = n - r;
int ans = 1;
for(int i = r; i >= 1; i--)
ans = ans * f[i] % mod;
for(int i = n; i >= n - r + 1; i--)
ans = ans * i % mod;
return ans;
}
int main ()
{
//预处理逆元
for(int i = 1; i <= maxn-10; i++)
f[i] = pow_mod(i, mod-2) % mod;
int n, m;
while(scanf("%d %d", &n, &m) != EOF)
{
int l = 0, r = 0;
int L = 0, R = 0;
int x;
for(int i = 0; i < n; i++)
{
scanf("%d", &x);
if(L >= x) l = L - x;
else if(R >= x) l = (R + x) & 1;
else l = x - R;
if(R + x <= m) r = R + x;
else if(L + x <= m) r = (((L + x)&1) == (m&1)) ? m : m-1;
else r = m - (L + x - m);
L = l; R = r;
}
int ans = C(m,L) % mod;;
int temp = ans;
for(int i = L+2; i <= R; i += 2)
{
temp = temp * f[i] % mod;
temp = temp * f[i-1] % mod;
temp = temp * (m - i + 1) % mod;
temp = temp * (m - i + 2) % mod;
ans = ans + temp % mod;
}
printf("%Id\n", ans % mod);
}
return 0;
}