pid=4869" target="_blank">Turn the pokers

大意：给出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 long

const 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<stdio.h>

#include<string.h>

#include<iostream>

#include<cmath>

using namespace std;

int a[100005];

__int64 pmod = 1000000009;

__int64 inv[100005];

__int64 ba[100005];

__int64 rba[100005];

#define M 100005

void 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;

}