生成函数和多项式
生成函数就是把一个序列写进一个多项式的系数，然后通过研究这个多项式来研究这个序列。序列可以是有限的，也可以是无限的。由于多项式乘法对应着系数的卷积，因此生成函数可以处理很多和卷积有关的问题。
定义
给定序列 \(\{f_{n}\}\)，定义多项式 \(F(x)\)
\[
F(x)=\sum_{i=0}f_ix^i
\]
为它的生成函数。生成函数之间的加法、减法、乘法就是通用的定义（对位相加，对位相减，系数卷积）。对于除法，定义多项式 \(F(x)\) 的乘法逆元 \(G(x)\) 为满足 \(F(x)G(x)=1\) 的多项式。若生成函数的常数项不为 \(0\)，那么它存在唯一的乘法逆元：
\[
\begin{cases}
b_0=\frac{1}{a_0}\\
b_n=-\frac{1}{a_0}\sum_{i=0}^{n-1}a_{n-i}b_i
\end{cases}
\]
封闭形式
把生成函数写成级数的形式有时不容易研究。这时可以把它写成封闭形式。
封闭形式是指通过有限次的初等运算（加、减、乘、除、乘方）和初等函数（指数函数、对数函数、三角函数、反三角函数）组合而成的数学表达式。
考虑一个例子，对于生成函数
\[
F(x)=1+x+x^2+\cdots=\sum_{i=0}^{+\infty}x^i
\]
考虑到 \(xF(x)+1=F(x)\)，通过移项可以得到：
\[
F(x)=\frac{1}{1-x}
\]
这样的东西叫做封闭形式。
更多封闭形式
等比数列 \(1,p,p^2,p^3,\cdots\) 的封闭形式为 \(F(x)=\frac{1}{1-px}\)；
斐波那契数列 \(0,1,1,2,3,5,8,13,\cdots\) 的封闭形式为 \(F(x)=\frac{x}{1-x-x^2}\)
给定正整数 \(m\)，求
\[
\sum_{\{a_i\}_{i=1}^n}\Bigl[\sum_{i=1}^na_i=m\Big]\prod_{i=1}^{n}fib(a_i)
\]
第一个 \(\sum\) 表示枚举所有长度任意，取值为正整数的序列；\(fib(n)\) 表示斐波那契数列的第 \(n\) 项。
\(m\le 10^{1000}\)，答案对 \(10^9+7\) 取模的结果。
设斐波那契数列的生成函数为 \(F(x)\)，注意到答案的生成函数 \(G(x)=\sum_{i=1}F^i(x)\) 即 \(G(x)=\frac{F(x)}{1-F(x)}\)。由 \(F(x)=\frac{x}{1-x-x^2}\) 得
\[
G(x)=\frac{x}{1-2x-x^2}
\]
于是得到 \(\{g_n\}\) 的递推式和初值：
\[
\begin{cases}
g_0=0\\
g_1=1\\
g_n=2g_{n-1}+g_{n-2}
\end{cases}
\]
解得特征根为 \(x_1=-1+\sqrt 2,~x_2=-1-\sqrt 2\)。带入初值解得通项公式为
\[
g_n=\frac{\sqrt 2}{4}\biggl(\Bigl(1+\sqrt 2\Big)^n-\Bigl(1-\sqrt 2\Big)^n\bigg)
\]
打表得 \(\sqrt 2\equiv 59713600\pmod{10^9+7}\)（其中一个解）。
代码
| #include<iostream>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int A = 1 + 59713600;
const int B = 1000000008 - 59713600;
const int C = 250000002l * 59713600 % MOD;
inline int qpow(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
inline int qpow(int a, string &b) {
int res = 1;
for(int i = b.size() - 1; i >= 0; i--) {
res = res * qpow(a, b[i] - '0') % MOD;
a = qpow(a, 10);
}
return res;
}
string n;
signed main() {
cin >> n;
cout << C * (qpow(A, n) - qpow(B, n) + MOD) % MOD << endl;
return 0;
}
|
有 \(n\) 对情侣来到电影院观看电影。在电影院，恰好留有 \(n\) 排座位，每排包含 \(2\) 个座位，共 \(2n\) 个座位。
现在，每个人将会随机坐在某一个位置上，且恰好将这 \(2n\) 个座位坐满。问恰好有 \(k\) 对情侣坐在同一排的方案数。
\(T\le 2\times 10^5,~n\le 5\times 10^6\)
说实话这题真不适合用生成函数，做法太垃圾了。但是既然原来在这，就把不用生成函数的做法也放在这吧。
发现只需求出 \(f_n\) 表示 \(n\) 对情侣有恰好 \(0\) 对和睦的方案数，那么询问的答案就是 \(\binom{n}{k}^2k!2^kf_{n-k}\)。考虑怎么求 \(f_n\)，考虑递推，考查坐在第一排椅子上的两个人，分讨他们是两个男的，两个女的，还是一男一女，这四种情况的方案数应该是相等的。然后考查他们的两个配偶坐在哪里，然后继续分讨她们旁边的两个人是不是一对，如果是，就从 \(f_{n-3}\) 转移，如果不是，就从 \(f_{n-2}\) 转移。总之就是这样，系数是好推的，式子太长了看代码吧。
代码
| #include<iostream>
#define int long long
using namespace std;
const int MOD = 998244353;
const int N = 5e6 + 10;
int T;
int n, k;
int f[N];
int inv[N], fact[N], ifact[N], pw2[N];
inline int C(int a, int b) { return fact[a] * ifact[a - b] % MOD * ifact[b] % MOD; }
signed main() {
inv[1] = fact[0] = ifact[0] = pw2[0] = 1;
for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;
for(int i = 1; i < N; i++) pw2[i] = pw2[i - 1] * 2 % MOD;
f[0] = 1, f[1] = 0;
for(int i = 2; i < N; i++) {
int tmp = i * (i - 1) % MOD;
f[i] = (i - 1) * (i - 1) * 2 % MOD * f[i - 2] % MOD;
(f[i] += (i - 1) * (i - 2) * 2 % MOD * f[i - 2] % MOD) %= MOD;
if(i >= 3) (f[i] += (i - 1) * (i - 2) % MOD * 8 % MOD * (i - 2) % MOD * f[i - 3] % MOD) %= MOD;
f[i] = f[i] * tmp % MOD * 4 % MOD;
}
cin >> T;
while(T--) {
cin >> n >> k;
int ans = C(n, k) * C(n, k) % MOD * pw2[k] % MOD * fact[k] % MOD * f[n - k] % MOD;
cout << ans << '\n';
}
return 0;
}
|