Codeforces Round #258 (Div. 2)E. Devu and Flowers

链接：http://codeforces.com/contest/451/problem/E

题意：给定n,s，n<=20，s<=10^14，有n种花，每种花有pi朵(pi<=10^12)，求有多少种取花的方案使得n种花之和为s。

分析：首先我们考虑忽略pi这个限制，那么我们就只要求C(s+n-1,n-1)即可。但是现在有pi这个限制怎么办呢？容斥即可，我们先考虑一部分花超过了pi的限制，那么我们就减去，但是我们在单独减去a类花超出和b类花超出的时候，对于a,b类花同时超出就减了一次，那么加一次回来，这就是容斥啦。O(n*2^n)

代码：

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=1020;
const int MAX=151;
const int MOD1=100000007;
const int MOD2=100000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=1000000007;
const ll INF=10000000010;
typedef unsigned long long ull;
ll s,f[22];
ll qpow(ll a,ll b) {
    ll ret=1;
    while (b) {
        if (b&1) ret=(ret*a)%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ret;
}
ll getC(ll n,ll k) {
    ll a=1,b=1;
    for (int i=0;i<k;i++) {
        a=a*((n-i)%MOD)%MOD;b=b*(i+1)%MOD;
    }
    return a*qpow(b,MOD-2)%MOD;
}
int main()
{
    int i,j,k,n;
    ll sum,ans=0;
    scanf("%d%I64d", &n, &s);
    for (i=0;i<n;i++) scanf("%I64d", &f[i]);
    for (i=0;i<(1<<n);i++) {
        sum=0;k=0;
        for (j=0;j<n;j++)
        if (i&(1<<j)) { sum+=f[j]+1;k++; }
        if (sum>s) continue ;
        if (k&1) ans-=getC(s-sum+n-1,n-1);
        else ans+=getC(s-sum+n-1,n-1);
        ans%=MOD;
    }
    printf("%I64d\n", (ans+MOD)%MOD);
    return 0;
}