学步园

题意：m 张牌，开始时全部正面朝下，翻转 n 次，每次翻转 xi 张牌，问最后的结果有多少种(0<n,m<=100000, 0<=Xi<=m)？

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4869

——>>假如最后有 a 张牌正面朝上，则它的结果有 C[m][a] 种（组合数），所以，只要求出最后可能有多少张牌正面朝上，再累加其组合数可行。。

1）求最后正面牌数的上下界；

2）以 2 为间隙进行枚举（可以取两个连续区间来试试，连续的区间最小变动为2，头尾变）。

#include <cstdio>

typedef long long LL;

const int MOD = 1000000009;
const int MAXN = 100000;

int n, m;
int L, R;
LL f[MAXN + 10];

void Init()
{
    L = R = 0;
}

void Read()
{
    int x;

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &x);
        int bufR = R;
        if (R + x <= m)
        {
            R += x;
        }
        else
        {
            if (L + x > m)
            {
                R = m - (L + x - m);
            }
            else
            {
                if ((m - L - x) & 1)
                {
                    R = m - 1;
                }
                else
                {
                    R = m;
                }
            }
        }
        if (x <= L)
        {
            L -= x;
        }
        else
        {
            if (x > bufR)
            {
                L = x - bufR;
            }
            else
            {
                if ((x - L) & 1)
                {
                    L = 1;
                }
                else
                {
                    L = 0;
                }
            }
        }
    }
}

void Gcd(LL a, LL b, LL& d, LL& x, LL& y)
{
    if (!b)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        Gcd(b, a % b, d, y, x);
        y -= a / b * x;
    }
}

LL Inv(int a, int n)
{
    LL ret = 0, d, y;

    Gcd(a, n, d, ret, y);

    return d == 1 ? (ret + n) % n : -1;
}

void GetF()
{
    f[0] = f[1] = 1;
    for (int i = 2; i <= MAXN; ++i)
    {
        f[i] = i * f[i - 1] % MOD;
    }
}

LL C(LL n, LL m)
{
    return f[n] * Inv(f[m] * f[n - m] % MOD, MOD) % MOD;
}

void Solve()
{
    LL ret = 0;

    for (int i = L; i <= R; i += 2)
    {
        ret = (ret + C(m, i)) % MOD;
    }

    printf("%I64d\n", ret);
}

int main()
{

    GetF();
    while (scanf("%d%d", &n, &m) == 2)
    {
        Init();
        Read();
        Solve();
    }
    return 0;
}