BZOJ3027 - Click Here
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
Solutions
WC时就切掉的题，结果到现在才写qwq
这种多次选择之间相互独立的题，范围又那么大，大概就是个生成函数了。
对于第$t$个糖果罐，易得其生成函数为$f(x) = \sum_{i=0}^{m_t} x^i = \frac{1 - x^{m_t + 1}}{1 - x}$
设答案的生成函数为$g(x)$，则$g(x)=\prod_{t=1}^n \frac{1 - x^{m_t + 1}}{1 - x} = (1-x)^{-n} \prod_{t=1}^n (1-x^{m_t +1})$
而题目要求的是$\sum_{i=a}^b [x^i]g(x)$，该式等价于$\sum_{i=1}^b [x^i]g(x) - \sum_{i=1}^{a - 1} [x^i]g(x)$
因此只需要将$g(x)$展开即可解决问题，考虑如何展开。
注意到题目中的$n$很小，因此可以暴力展开$\prod_{i=1}^n (1-x^{m_i +1})$。此时$g(x) = \sum a_ix^{i}(1-x)^{-n}$
这样就转换成了对一个二项式求其系数之和，设$h(x)=a_ix^{i}(1-x)^{-n}$
对于一个固定的$i$，有$h(x) = a_ix^i \sum_{0 \leq k} \binom {-n}{k}(-x)^k = \sum_{i \leq k} a_i \binom{n-1+k-i}{n-1}x^k$
则$\sum_{k=1}^b [x^k]h(x) = \sum_{k=i}^b a_i \binom{n-1+k-i}{n-1} = \sum_{k=0}^{b-i} a_i \binom{n-1+k}{n-1} = a_i \binom{n+b-i}{n}$
因此$\sum_{i=1}^b [x^i]g(x) = \sum a_i\binom{n+b-i}{n}$
直接统计即可，时间复杂度$O(n2^n)$
CODE
CODE - Click Here