codeforces 336D. Vasily the Bear and Beautiful Strings 组合数学 dp

题意：

给出n,m,g，求好串的个数

0 <= n,m <= 10^5,n + m >= 1,0 <= g <= 1

好串的定义：

1.只由0，1组成，并且恰好有n个0，m个1

2.串的value = g

串的value的计算方式：

每次将最后2个字符替换，直至串的长度为1，该字符就是串的value

00 -> 1,   01,11,10 -> 0

solution:

首先，总方案数 = C(n + m, m)

m = 0时，特殊判断

设f(n,m)为n个0，m个1时，value为1的方案数

g(n,m)为n个0，m个1时，value为0的方案数

则f(n,m) + g(n,m) = C(n+m,m)

观察1个长度 > 1的串，若该串的value = 1

则str[1] = 0,且value(str[2] ~ str[n]) = 0

则有f(n,m) = g(n-1,m) = C(n-1+m,m) - f(n-1,m)

注意到，f的值与m无关(m固定后)

则设f(i) 为有i个0，m个1时，value = 1的方案数

则有f(i+1) = C(i+m,m) - f(i)

init: m=1,f(0) = 1

　　m>1,f(0) = 0

g = 1,ans = f(n)

g = 0,ans = C(n+m,m) - f(n)

  //File Name: cf336D.cpp
  //Author: long
  //Mail: [e-mail]
  //Created Time: 2016年02月17日 星期三 20时38分47秒

#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>

#define LL long long

using namespace std;

const int MAXN = 1e5+;
const int MOD = 1e9+;

LL f[MAXN];
LL jie[MAXN << ];

LL qp(LL x,LL y)
{
    LL res = 1LL;
    while(y){
        if(y & )
            res = res * x % MOD;
        x = x * x % MOD;
        y >>= ;
    }
    return res;
}

LL comb(int x,int y)
{
    if(y <  || y > x)
        return ;
    if(y ==  || y == x)
        return ;
    return jie[x] * qp(jie[y] * jie[x - y] % MOD,MOD  - ) % MOD;
}

void init()
{
    jie[] = ;
    for(int i=;i<MAXN * ;i++){
        jie[i] = jie[i-] * i % MOD;
    }
}

void solve(int n,int m,int g)
{
    if(m == ){
        int num_0 = ,num_1 = ;
        if(n % )
            num_0 = ;
        else
            num_1 = ;
        printf("%d\n",g ? num_1:num_0);
        return ;
    }
    init();
    memset(f,,sizeof f);
    f[] = (m ==  ? : );
    for(int i=;i<n;i++){
        f[i+] =((comb(i + m, i) - f[i] + MOD ) % MOD + MOD) % MOD;
    }
    LL ans = f[n];
    if(!g)
        ans = ((comb(n+m,n) - f[n] + MOD) % MOD + MOD) % MOD;
    printf("%d\n",(int)ans);
    return ;
}

int main()
{
    int n,m,g;
    while(~scanf("%d %d %d",&n,&m,&g)){
        solve(n,m,g);
    }
    return ;
}