BZOJ 3027 Sweets 生成函数，容斥

攻城狮一鸣技术 2022年11月7日

0 收藏 436 点赞 982 浏览 903 个字

Description

John得到了n罐糖果。不同的糖果罐，糖果的种类不同（即同一个糖果罐里的糖果种类是相同的，不同的糖果罐里的糖果的种类是不同的）。第i个糖果罐里有 mi个糖果。John决定吃掉一些糖果，他想吃掉至少a个糖果，但不超过b个。问题是John 无法确定吃多少个糖果和每种糖果各吃几个。有多少种方法可以做这件事呢？

Input

从标准输入读入每罐糖果的数量，整数a到b

John能够选择的吃掉糖果的方法数（满足以上条件）

Output

把结果输出到标准输出（把答案模 2004 输出）

1<=N<=10,0<=a<=b<=10^7,0<=Mi<=10^6

Sample Input

2 1 3
3
5

Sample Output

HINT

(1,0),(2,0),(3,0),(0,1),(0,2),(0,3),(1,1),(1,2),(2,1)

解法：

typedef long long LL;
const int mod = 2004;
int n, a, b, ans, m, v[20];
int C(int n,int m)
{
    if (n<m) return 0;
    LL t=1; LL p1=1;
    for (int i=1;i<=m;i++) p1=p1*i;
    LL mod2=(LL)mod*p1;
    for (int i=n-m+1;i<=n;i++) t=(LL)t*i%mod2;
    return (t/p1)%mod;
}
void dfs(int x, int cnt, int sum){
    if(x==n+1){
        if(cnt&1) ans-=C(n+m-sum,n);
        else ans+=C(n+m-sum,n);
        ans %= mod;
        return;
    }
    dfs(x+1,cnt,sum);
    dfs(x+1,cnt+1,sum+v[x]);
}
int f(int x){
    ans=0;
    m=x;
    dfs(1,0,0);
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1; i<=n; i++) scanf("%d", &v[i]), v[i]++;
    int ans = f(b)-f(a-1);
    printf("%d\n", (ans%mod+mod)%mod);
    return 0;
}