zoj 3638古典的反発原理

n種類の品物があって、m個を取って出てきて、もしそれぞれの品物の数量が制限がないならば、答えはC(m,m+n-1)---多重セットのカウント
1.現在、制限されているものはxより大きく、解決方法はm-=x後に元の方法で解決する.
2.制限、物品a 1はx 1より小さく、a 2はx 2より小さく、......
反発問題に変換
反発原理には2つの書き方を添付する

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define mod 100000007

ll pow_mod(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=(res*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return res;
}
ll comb(ll n,ll m)
{
    if(n<0 || m<0 || m>n) return 0;
    ll up=1,down=1;
    for(ll i=n;i>n-m;--i)
        up=(up*i)%mod;
    for(ll i=1;i<=m;++i)
        down=(down*i)%mod;
    ll res=up*pow_mod(down,mod-2)%mod;
    return res;
}
int a[50],cnt;
ll dfs(int cur,ll down,ll up)
{
    ll res=0;
    for(int i=cur;i<cnt;++i)
    {
        res += comb(down-a[i],up);
        res -= dfs(i+1,down-a[i],up);
    }
    return res;
}
ll n,m;
char s1[1000],s2[1000],str[1000];
int main ()
{
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        if(n==0) break;
        cnt=0;
        int num;
        gets(str);
        bool flag=true;
        while(1)
        {
            if(!gets(str)) break;
            if(strlen(str)<2) break;
            sscanf(str,"%s%s%s%d",s1,s1,s2,&num);
            if(s1[0]=='g')
            {
                m-=num+1; // greater than  or equal to num+1

            }
            else
            {
                // <num
                a[cnt++]=num;
                if(num==0) // less than 0, impossible
                    flag=false;
            }
        }
        if(flag)
        {
            /*ll ans=comb(n+m-1,n-1)-dfs(0,n+m-1,n-1);
            ans=(ans%mod+mod)%mod;*/
            ll ans=comb(n+m-1,n-1);
            int tot=(1<<cnt)-1;
            for(int i=1;i<=tot;++i) //        2^(cnt)   
            {
                int ones=0;
                ll temp=0;
                for(int j=0;j<cnt;++j)
                    if((i>>j)&1)
                {
                    temp+=a[j];
                    ones++;
                }
                if(ones&1)
                    ans=(ans-comb(n+m-1-temp,n-1))%mod;
                else ans=(ans+comb(n+m-1-temp,n-1))%mod;
            }
            ans=(ans%mod+mod)%mod;
            printf("%lld
",ans);
        }
        else printf("0
");
    }
    return 0;
}