Codeforces336D Vasily the Bear and Beautiful Strings

题意：输入n，m，g代表长度为n+m的字符串且有n个0，m个1，一个字符串的权值定义为对末两位的字符每次把该字符串的最后两位变成一位（如果是两个00就变成11，否则变成00），最后只剩一位即为该字符串的权值，问权值为g的字符串个数

题解：组合数学，可以发现权值为1的字符串钱吗必定有0

所以有两种情况，第一种情况是有奇数个0+1+任意的数，第二种情况是偶数个0+1

特判n==0和m==0的情况，组合数统计一下就可以

#include <bits/stdc++.h>
#define maxn 200010
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
const ll mod = 1e9+7;
ll fac[maxn], inv[maxn];
void init(){
    fac[0] = inv[0] = inv[1] = 1;
    for(ll i=1;i<maxn;i++) fac[i] = fac[i-1]*i%mod;
    for(ll i=2;i<maxn;i++)inv[i]=mod-(ll)(mod/i)*inv[mod%i]%mod;
    for(ll i=1;i<maxn;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
}
ll c(ll a,ll b){
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
    ll n, m, q, ans = 0, g;
    scanf("%lld%lld%lld", &n, &m, &g);
    init();
    if(n == 0){
        if(m == 1) printf("%d
", g);
        else printf("%d
", !g);
    }
    else if(m == 0){
        if(n%2) printf("%d
", !g);
        else printf("%d
", g);
    }
    else{
        for(ll i=1;i<=n;i+=2)
            if(n+m-i-1 != 0)
            ans = (ans+c(n+m-i-1, m-1))%mod;
        if(m == 1&&n%2 == 0) ans++;
        printf("%lld
", g?((ans+mod)%mod):((c(n+m, n)-ans+mod)%mod));
    }
    return 0;
}