生成函数

给定一个无穷序列 $a_0,a_1,a_2,\cdots,a_n,\cdots$

定义一个函数 $g(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots ,-1<x<1$ ，则 $g(x)$ 称为序列的一个生成函数

生成函数就是将序列映射到多项式上，这样就可以用函数和多项式的相关方法计算序列

例：有三个砝码，重量分别为 1g,2g,3g ，问一共可以凑出那些重量，每个重量有多少种凑出方式

乘法原理 $\Longleftrightarrow$ 多项式乘法

对于第一个砝码，重量为 0 有一种选择，重量为 1 有一种选择，其余为零种选择，因此其对应的序列中 $a_0=1,a_1=1,a_2=a_3=\cdots=0$，其对应的生成函数 $f_1(x)=1+x$

对于第二个砝码 $a_0=a_2=1$，其对应的生成函数 $f_2(x)=1+x^2$

对于第三个砝码 $a_0=a_3=1$，其对应的生成函数 $f_3(x)=1+x^3$

整体的生成函数 $f(x)=f_1(x)f_2(x)f_3(x)=(1+x)(1+x^2)(1+x^3)=1+x+x^2+2x^3+x^4+x^5+x^6$

$a_0=1,a_1=1,a_2=1,a_3=2,a_4=1,a_5=1,a_6=1$，因此凑出来 0,1,2,4,5,6 的方案数为 1，凑出来 3 的方案数为 2

生成函数求解思路：原问题 $\to$ 若干个子问题 $\to$ 子问题序列 $\to$ 子问题生成函数 $\to$ 原问题生成函数 $\to$ 原问题序列

例：1g 的砝码有两个，2g 的砝码有无限个，3g 的砝码有一个，问一共可以凑出那些重量，每个重量有多少种凑出方式

$f_1(x)=1+x+x^2$

$f_2(x)=1+x^2+x^4+\cdots$

$f_3(x)=1+x^3$

$f(x)=f_1(x)f_2(x)f_3(x)$

例：有 $n$ 种苹果，每种苹果有无限个，问选出来 $k$ 个苹果的方案数

$f_i(x)=1+x+x^2+x^3+\cdots=\frac{1-x^n} {1-x}$

由于 $-1<x<1$，则 $\lim_{x \to \infty} x^n=0$，则$f_i(x)=\frac 1 {1-x}$

$f(x)=\frac 1 {(1-x)^n}=a_0+a_1x+x_2x^2+\cdots+a_nx^n+\cdots$

其中$a_k=C_{k+n-1}^{n-1} $

以下证明 $f(x)=\frac 1 {(1-x)^n}=a_0+a_1x+a_2x^2+\cdots +a_nx^n$，其中 $a_k=C_{k+n-1}^{n-1}$

$f(x)=\frac 1 {(1-x)^n}=(\frac 1 {1-x})^n$

由泰勒级数，$\frac 1 {1-x}=1+x+x^2+\cdots$，$f(x)=(\frac 1 {1-x})^n=(1+x+x^2+x^3+\cdots)^n$

由组合计数，$x^k$ 的系数 $a^k=\sum_{i=1}^{k} C_n^iC_{k-1}^{i-1}$（即选择 1~k 个括号内的取值不为 1，对于 $i=t$ ，在 $n$ 个括号中选 $t$ 个，将幂次 $k$ 分到这 $t$ 个括号中，保证每个括号取值不为 1 的方案数）

$\sum_{i=1}^{k} C_n^iC_{k-1}^{i-1}=\sum_{i=1}^{k} C_n^iC_{k-1}^{k-i}$

由于 $C_n^iC_{k-1}^{k}=0$，因此 $\sum_{i=1}^{k} C_n^iC_{k-1}^{k-i}=\sum_{i=0}^kC_n^iC_{k-1}^{k-i}$

则由范德蒙恒等式 $\sum_{i=0}^kC_m^iC_{n}^{k-i}=C_{m+n}^{k}$，$a_k=\sum_{i=0}^kC_n^iC_{k-1}^{k-i}=C_{n+k-1}^{k-i}$

例题：AcWing 3132. 食物

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！

我们暂且不讨论他有多么睿智，他又幻想了他应该带一些什么东西。

理所当然的，你当然要帮他计算携带 $ N $ 件物品的方案数。

他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等

当然，他又有一些稀奇古怪的限制，每种食物的限制如下：

• 承德汉堡：偶数个。
• 可乐：$ 0 $ 个或 $ 1 $ 个。
• 鸡腿：$ 0 $ 个，$ 1 $ 个或 $ 2 $ 个。
• 蜜桃多：奇数个。
• 鸡块：$ 4 $ 的倍数个。
• 包子：$ 0 $ 个，$ 1 $ 个，$ 2 $ 个或 $ 3 $ 个。
• 土豆片炒肉：不超过一个。
• 面包：$ 3 $ 的倍数个。

注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以‘个’为单位（反正是幻想嘛），只要总数加起来是 $ N $ 就算一种方案。

因此，对于给出的 $ N $，你需要计算出方案数，并对 $ 10007 $ 取模。

输入格式

一个整数 $ N $。

输出格式

一个整数，表示方案数对 $ 10007 $ 取模后的结果。

数据范围

$ 1 \le N \le 10^{500} $

输入样例1：

1

1

输出样例1：

1

1

输入样例2：

1

5

输出样例2：

1

35

分析：

$f_1(x)=1+x^2+x^4+\cdots=\frac 1 {1-x^2}$

$f_2(x)=1+x=\frac {1-x^2} {1-x}$

$f_3(x)=1+x+x^2=\frac {1-x^3} {1-x}$

$f_4(x)=x+x^3+x^5+\cdots=x\frac 1 {1-x^2} = \frac x {1-x^2}$

$f_5(x)=1+x^6+x^8+\cdots=\frac 1 {1-x^4}$

$f_6(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}$

$f_7(x)=1+x=\frac{1-x^2}{1-x}$

$f_8(x)=1+x^3+x^6+\cdots=\frac 1 {1-x^3}$
$$
\begin{array}{l}
f(x)\
=f_1(x)f_2(x)f_3(x)f_4(x)f_5(x)f_6(x)f_7(x)f_8(x)\
=\frac 1 {\bcancel{1-x^2}}\frac {\bcancel{1-x^2}} {1-x}\frac {\bcancel{1-x^3}} {1-x}\frac x {\bcancel{1-x^2}}\frac 1 {\bcancel{1-x^4}}\frac{\bcancel{1-x^4}}{1-x}\frac{\bcancel{1-x^2}}{1-x}\frac 1 {\bcancel{1-x^3}}\
=\frac x {(1-x)^4}
\end{array}
$$
因此要求 $f(x)$ 展开式中 $x^N$ 项的系数
$$
\begin{array}{l}
f(x)\
=\frac x {(1-x)^4}\
=x\frac 1 {(1-x)^4}\
=x(\sum_{i=0}^\infty a_ix^i) &a_i=C_{i+4-1}^{4-1}\
=\sum_{i=0}^{\infty} C_{i+4-1}^{4-1} x^{i+1}
\end{array}
$$
因此 $x^N$ 的系数为 $C_{(N-1)+4-1}^{4-1}=C_{N+2}^3=\frac{(N+2)(N+1)N} {1\times 2\times 3}$

1
2
3
4
5
6
7
8
9
10
11
12
13

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    char x;
    while(cin >> x){
        n=10*n+x-'0';
        n%=10007;
    }
    cout << 1ll*(n+2)*(n+1)*n/6%10007;
    return 0;
}