糖果

题意

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

---

思路

第i种糖果的生成函数是\(1+x+...+x^{m_i}\)，乘在一起就是\(\Pi 1+x+...+x^{m_i}=\frac{\Pi (1-x^{m_i+1})}{(1-x)^n}\)

本题的答案显然为前b项系数和减去前a-1项系数和。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
    #define int long long

    const int N=101;
    const int MOD=2004;

    int n,a,b;
    int mul=1;
    int m[N];

    inline int C (int x,int y) {
        if (x<y) return 0;
        int res=1;
        for (register int i=x-y+1; i<=x; ++i) {
            res=i%(mul*MOD)*res%(mul*MOD);
        }
        return (res/mul)%MOD;
    }
    int dfs (int pos,int a,int b,int mm) {
        if (pos==n+1) return a*C(n+mm-b,n)%MOD;
        return (dfs(pos+1,a,b,mm)+dfs(pos+1,-a,b+m[pos]+1,mm))%MOD;
    }

    inline void MAIN () {
        read(n),read(a),read(b);
        for (register int i=1; i<=n; ++i) mul*=i;
        for (register int i=1; i<=n; ++i) read(m[i]);
        write(((dfs(1,1,0,b)-dfs(1,1,0,a-1))%MOD+MOD)%MOD);
    }

    #undef int
}

int main () {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    Project::MAIN();
}