博客园食用更佳
关注洛谷谢谢喵~
先看例题：
BZOJ3028 食物
先看数据范围，n≤10500n \le 10^{500}n≤10500，可能会想到矩阵加速。
dpidp_idpi 表示选了 iii 件物品的方案数，很明显，对于只能选偶数类，奇数类，444 的倍数类，333 的倍数类，需要记录以前分别 mod 2,3,4\bmod 2,3,4mod2,3,4 的前缀和，我们考虑先只选这些有倍数限制的方案，因为这些可以从前面转移，而像只能选 0∼30 \sim 30∼3 个之类的，是一次性消耗品，发现可以最后再选。那么转移矩阵也就是 11×1111 \times 1111×11 的，最后乘上 log10500\log 10^{500}log10500 也就约等于 166016601660 左右。求出 dpndp_ndpn
之后就可以暴力枚举剩下的食物分别选几个，再从前面转移即可。似乎能过？
但是这样还是太慢了，有没有更快又更简单不用构造转移矩阵的方法呢，有的兄弟有的，我们生成函数就可以登场了。
我们发现，假如现在选 aaa 个的方案数为 bbb，考虑选不选可乐的情况，那么选可乐就会变成选 a+1a+1a+1 个的方案数为 bbb；不选即为选 aaa 个的方案数为 bbb。这个似乎很像一个乘法分配律？将选 aaa 个的方案数为 bbb 换一个形式表达：b×xab \times x^ab×xa，选不选可乐的情况即为 (x+1)(x+1)(x+1)，将两者乘在一起变为 b×xa×(x+x0)b \times x^a \times(x+x^0)b×xa×(x+x0)，化简变为 b×xa+b×xa+1b \times x^a + b \times x^{a+1}b×xa+b×xa+1，发现
xxx 的幂即为选了多少个，其系数即为方案数。
那么显然有初值 x0x^0x0，即选 000 个的方案数为 111。那每种方案将其转化分别变为：
* 汉堡：∑i=0∞x2i\sum_{i=0}^{\infty} x^{2i}∑i=0∞ x2i
* 可乐：x0+x1x^0+x^1x0+x1
* 鸡腿：x0+x1+x2x^0+x^1+x^2x0+x1+x2
* 蜜桃多：∑i=0∞x2i****um_{i=0}^{\infty} x^{2i+1}∑i=0∞ x2i+1
* 鸡块：∑i=0∞x4i\sum_{i=0}^{\infty} x^{4i}∑i=0∞ x4i
* 包子：x0+x1+x2+x3x^0+x^1+x^2+x^3x0+x1+x2+x3
* 土豆片炒肉：x0+x1x^0+x^1x0+x1
* 面包：∑i=0∞x3i\sum_{i=0}^{\infty} x^{3i}∑i=0∞ x3i
发现乘上一个 xax^axa 就相当于又选了 aaa 个数，而对于有多种选择的物品，我们用加法将其加起来，之后用乘法分配律即可计算。所以答案即为上面这些式子乘在一起，取 xnx^nxn 的系数。
但是发现有一些式子是有无穷项的，无法乘在一起，所以我们考虑求出其封闭形式。
> 引理 111：∑i=0∞xi=11−x(∣x∣<1)\sum_{i=0}^{\infty} x^i=\dfrac{1}{1-x}(|x|<1)∑i=0∞ xi=1−x1 (∣x∣<1)
该引理被称为几何级数公式。证明考虑等比数列求和公式，原式可变为 x∞−1x−1\dfrac{x^\infty-1}{x-1}x−1x∞−1 ，由于 ∣x∣<1|x|<1∣x∣<1，所以 x∞x^\inftyx∞ 趋近 000，故原式等于 11−x\dfrac{1}{1-x}1−x1 。
这里可能有读者疑惑，可以保证 ∣x∣<1|x|<1∣x∣<1 吗？生成函数研究的是 xxx 在 000 的邻域的情况，所以有 ∣x∣<1|x|<1∣x∣<1。
同理 ∑i=0∞x2i=11−x2,∑i=0∞x4i=11−x4\sum_{i=0}^{\infty} x^{2i}=\dfrac{1}{1-x^2},\sum_{i=0}^{\infty} x^{4i}=\dfrac{1}{1-x^4}∑i=0∞ x2i=1−x21 ,∑i=0∞ x4i=1−x41 。
那么重新写出：
* 汉堡：11−x2\frac{1}{1-x^2}1−x21
* 蜜桃多：x1−x2\frac{x}{1-x^2}1−x2x
* 鸡块：11−x4\frac{1}{1-x^4}1−x41
* 面包：11−x3\frac{1}{1-x^3}1−x31
那么最后乘法就比较简单了，这里直接给出化简之后的结果 x×(x−1)−4x \times (x-1)^{-4}x×(x−1)−4，但是此时我们依然不知道 xnx^nxn 的系数。
设 α\alphaα 为实数，iii 为整数，则定义：
(αi)={0,(ilt;0)1,(i=0)α(α−1)⋯(α−i+1)i!,(igt;0){\alpha \choose i}=\begin{cases}0,&(i<0)\\1,&(i=0)\\\frac{\alpha(\alpha-1)\cdots(\alpha-i+1)}{i!},&(i>0)\end{cases} (iα )=⎩⎨⎧ 0,1,i!α(α−1)⋯(α−i+1) , (i(i=0)(i lt;0)gt;0)
> 引理 222：(x+y)α=∑i=0∞(αi)xiyα−i(x+y)^{\alpha}=\sum_{i=0}^{\infty} {\alpha \choose i} x^i y^{\alpha-i}(x+y)α=∑i=0∞ (iα )xiyα−i
这个引理被称为广义牛顿二项式定理，读者自证不难。
则原式变为：x×∑i=0∞(−4i)xi(−1)−4−ix \times \sum_{i=0}^{\infty} {-4\choose i}x^i(-1)^{-4-i}x×∑i=0∞ (i−4 )xi(−1)−4−i。根据定义 (αi)\alpha\choose i(iα ) 可以先将分子中的 (−1)i(-1)^i(−1)i 提出来，变为 (−1)i×(−α+i−1)(−α+i)⋯−αi!=(−1)i×(i−α−1i)(-1)^i \times \dfrac{(-\alpha+i-1)(-\alpha+i)\cdots-\alpha}{i!}=(-1)^i \times
{{i-\alpha-1}\choose i}(−1)i×i!(−α+i−1)(−α+i)⋯−α =(−1)i×(ii−α−1 )，将 α=4\alpha=4α=4 带入，变为 (−4i)=(i+3i){-4\choose i}={i+3\choose i}(i−4 )=(ii+3 )。然后继续化简：
x×∑i=0∞(−4i)xi(−1)−4−i=x×∑i=0∞(i+3i)xi(−1)−4−i(−1)i=∑i=0∞(i+3i)xi+1=∑i=1∞(i+23)xi=∑i=1∞i(i+1)(i+2)6×xi\begin{aligned}&x \times \sum_{i=0}^{\infty} {-4\choose i}x^i(-1)^{-4-i}\\&= x \times \sum_{i=0}^{\infty} {i+3\choose i} x^i(-1)^{-4-i}(-1)^i\\&=\sum_{i=0}^{\infty} {i+3\choose i}
x^{i+1}\\&=\sum_{i=1}^{\infty} {i+2\choose 3}x^i\\&= \sum_{i=1}^{\infty} \dfrac{i(i+1)(i+2)}{6} \times x^i \end{aligned} x×i=0∑∞ (i−4 )xi(−1)−4−i=x×i=0∑∞ (ii+3 )xi(−1)−4−i(−1)i=i=0∑∞ (ii+3 )xi+1=i=1∑∞ (3i+2 )xi=i=1∑∞ 6i(i+1)(i+2) ×xi
化简完成，由此我们知道了 xnx^nxn 系数为 n(n+1)(n+2)n(n+1)(n+2)n(n+1)(n+2)，这就是生成函数的作用，能让我们快速求出某个方案数。
[CEOI 2004] SWEETS
依旧采用上一题的思路，考虑将 xkx^kxk 表示选 kkk 颗糖果，其系数为方案数。那么每个糖果罐的方程即为 ∑j=0mixj\sum_{j=0}^{m_i} x^j∑j=0mi xj，代表分别选 0,1,⋯ ,mi0,1,\cdots,m_i0,1,⋯,mi 个糖果的方案数。
发现 mim_imi 的值比较大，那么就将原方程转为封闭形式，设 fi=∑j=0mixjf_i=\sum_{j=0}^{m_i} x^jfi =∑j=0mi xj，则 fi×x=∑j=1mi+1xjf_i \times x =\sum_{j=1}^{m_i+1} x^jfi ×x=∑j=1mi +1 xj，两者相减有 fi×(x−1)=xmi+1−1f_i \times (x-1)=x^{m_i+1}-1fi ×(x−1)=xmi +1−1，故 fi=xmi+1−1x−1f_i=\dfrac{x^{m_i+1}-1}{x-1}fi =x−1xmi +1−1 。
则所有方程的积即为 (1−x)−n×∏i=1n(1−xmi+1)(1-x)^{-n} \times \prod_{i=1}^n (1-x^{m_i+1})(1−x)−n×∏i=1n (1−xmi +1)，由于 nnn 最大为 101010，所以后面的乘积最多有 210=10242^{10}=1024210=1024 项，所以可以直接暴力合并，而前面的次方可以用类似上题使用广义牛顿二项式定理变为：∑i=0∞(i+n−1n−1)xi\sum_{i=0}^{\infty}{i+n-1\choose n-1} x^i∑i=0∞ (n−1i+n−1
)xi，所以在不考虑后面的多项式的情况下，xix^ixi 的系数为 (i+n−1n−1){i+n-1\choose n-1}(n−1i+n−1 )。
设后面的多项式为 g(x)=a1xb1+a2xb2+⋯+apxbpg(x)=a_1x^{b_1} + a_2x^{b_2}+\cdots+a_px^{b_p}g(x)=a1 xb1 +a2 xb2 +⋯+ap xbp ，我们考虑其中一项 jjj 对答案（即选 1∼a1\sim a1∼a 个糖的方案数）的贡献：aj×∑i=0a−bj(i+n−1i)=aj×(n+a−bja−bj)=aj×(n+a−bjn)a_j \times \sum_{i=0}^{a-b_j} {i+n-1\choose i}=a_j \times {n+a-b_j \choose a-b_j}=a_j \times
{n+a-b_j \choose n}aj ×∑i=0a−bj (ii+n−1 )=aj ×(a−bj n+a−bj )=aj ×(nn+a−bj )。证明考虑 (nm)=(n−1m−1)+(n−1m){n \choose m}={n-1 \choose m-1}+{n-1 \choose m}(mn )=(m−1n−1 )+(mn−1 )。具体地，将第一项 (n−10){n-1\choose 0}(0n−1 ) 改为 (n0){n\choose 0}(0n )，然后就可以向后一直推下去了。
那么问题来到了求一个组合数模 200420042004 的值，(nm)=n!(n−m)!m!{n \choose m}=\dfrac{\frac{n!}{(n-m)!}}{m!}(mn )=m!(n−m)!n! ，显然分子可以预处理出来，设分子为 xxx，同时 x=2004×p×m!+q×m!(q<2004)x=2004 \times p \times m! + q \times m!(q<2004)x=2004×p×m!+q×m!(q<2004)，因为 m!∣xm!|xm!∣x，所以将 xxx 分解后，肯定每一项都包含 m!m!m!，那么现在只需要将 xxx 对 2004×m!2004
\times m!2004×m! 取模然后除以 m!m!m! 即可。
