大意：给出n次操作，给出m个扑克。然后给出n个操作的个数a[i]，每一个a[i]代表能够翻的扑克的个数，求最后可能出现的扑克的组合情况。
Hint
Sample Input：
3 3
3 2 3
For the this example:
0 express face down,1 express face up
Initial state 000
The first result:000->111->001->110
The second result:000->111->100->011
The third result:000->111->010->101
So, there are three kinds of results(110,011,101)
思路：要说清楚不是非常easy。官方题解是这么说的：
“终于的结果一定是连续出现的，仅仅须要求出终于的区间。
由于假设对同一张牌进行两次操作，牌的状态不改变。故牌的翻转次数一定是降低偶数次。假设全部数的和是奇数，那么终于结果也一定是奇数。同理，偶数也是一样的。
所以仅仅要递推求出最后的区间，计算sum（C（xi。m）（i=0，1，2。。。））。m是总牌数，xi是在区间内连续的奇数或偶数，在模10^9+9就是终于的答案。”
#define LL long longconst int MOD = 1000000009;LL J[100005];void Init(){///初始化阶乘表 J[0] = 1; for(int i = 1; i <= 100005; ++i){ J[i] = J[i-1]*i%MOD; }}///高速幂取模LL modexp(LL a,LL b,LL n){ LL ret=1; LL tmp=a; while(b) { if(b&1) ret=ret*tmp%n; tmp=tmp*tmp%n; b>>=1; } return ret;}///求组合数 逆元 C(n, m) = n! * (m!*(n-m)!)^(MOD-2)LL C(LL n, LL m){ return J[n]*modexp(J[m]*J[n-m]%MOD, MOD-2, MOD)%MOD;}int a[100010];int main(){ int n, m; Init(); while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < n; ++i) { scanf("%d", &a[i]); } int l = 0; int r = 1; int t = 0; for(int i = 0; i < n; ++i) { int ll = min(abs(l-a[i]), abs(r-a[i])); if(l <= a[i] && r >= a[i]) { ll = 0; } int rr = max(m-abs(l+a[i]-m), m-abs(r+a[i]-m)); if(l <= m-a[i] && r >= m-a[i]) { rr = m; } t = (t+a[i])%2; l = ll; r = rr; } long long ans = 0; for(int i = l; i <= r; ++i) { if(i%2 == t) { ans += C(m, i); ans %= MOD; } } printf("%I64d\n", ans); } return 0;} //官方题解的解组合#include#include #include #include using namespace std;int a[100005];__int64 pmod = 1000000009;__int64 inv[100005];__int64 ba[100005];__int64 rba[100005];#define M 100005void pre() { inv[0] = inv[1] = 1; ba[0] = ba[1] = 1; rba[0] = rba[1] = 1; for (int i = 2; i < M; i++) { inv[i] = ((pmod - pmod / i) * inv[pmod % i]) % pmod; ba[i] = (ba[i - 1] * i)%pmod; rba[i] = (rba[i - 1] * inv[i])%pmod; }}__int64 C(int n, int k) { return (ba[n] * rba[k] % pmod )* rba[n - k] % pmod;}