跳转至

生成函数和多项式

萌新刚学 OI，可能有一堆笔误，请见谅。

特征根法求序列通项

考虑常系数齐次线性递推

\[ a_n=\sum_{i=1}^{k}a_{n-i}b_i~\text{ for }n\ge k \]

我们已知 \(b_i\)，不知道 \(a_i\) 的初始值（前 \(k\) 项），求 \(a_i\) 的通解。

首先感性理解 \(a_i\) 的解是一个 \(k\) 阶的线性空间（可以分解为 \(k\) 组基，相互之间线性无关并且可以线性组合出所有解），因为解肯定是线性空间，并且前 \(k\) 项的值唯一确定一组解，所以阶数应该是 \(k\)。

然后，考虑求出 \(k\) 组特解。假设特解是 \(a_n=r^{n}\) 的形式（\(r\) 是一实数），那么根据递推式，有

\[ r^n=\sum_{i=1}^{k}r^{n-i}b_i~\text{ for }n\ge k \]

同时除以 \(r^{n-k}\)：

\[ r_k=\sum_{i=1}^{k}r^{k-i}b_i \]

这是一个 \(k\) 次方程。考虑解出 \(k\) 个根 \(r_0\sim r_{k-1}\)，网上有详细分析重根和虚根的情况，总是可以产生 \(k\) 个线性无关的特解（其实是我不会）。代入初值解出系数，即可获得通项公式。

定义

给定序列 \(f_{0\sim ?}\)，定义其生成函数 \(F(x)\) 为幂级数（多项式）

\[ F(x)=\sum_{i=0}f_ix^i \]

序列可以是有限的，也可以是无限的。定义生成函数的加法、减法为对位相加减，乘法为卷积，结果都仍然是生成函数。注意这里的 \(x\) 并不能取某一具体数值，而是一个占位符，方便我们定义生成函数的运算。我们重点关注的是多项式的系数。

乘法的单位元是 \(1\)（常数项等于 \(1\)，其他项为 \(0\) 的多项式）。若生成函数的常数项不为 \(0\)，那么它存在乘法逆元。这个条件显然必要，下面给出构造证明其充分性：

对于生成函数 \(F(x)=\sum_{i=0}a_ix^i~(a_0\ne 0)\)，设其乘法逆 \(F^{-1}(x)=\sum_{i=0}b_ix_i\)。那么由定义得 \(b_0=(a_0)^{-1}\)。对于剩下的部分，考虑逐位递推：

\[ b_i=-\frac{1}{a_0}\sum_{j=0}^{i-1}a_{i-j}b_j \]

这样显然 \(F(x)*F^{-1}(x)=1\)。

封闭形式

考虑一个例子，对于生成函数

\[ F(x)=1+x+x^2+\cdots=\sum_{i=0}x^i \]

考虑到 \(xF(x)+1=F(x)\)，通过移项可以得到：

\[ F(x)=\frac{1}{1-x} \]

这样的东西叫做封闭形式。

更多生成函数的封闭形式

等比数列 \(1,p,p^2,p^3,\cdots\)，满足 \(pxF(x)+1=F(x)\)，因此其封闭形式为

\[ F(x)=\frac{1}{1-px} \]

不知道叫啥的东西 \(F(x)=\sum_{i=0}x^{ip}\)，满足 \(x^pF(x)+1=F(x)\)，因此其封闭形式为

\[ F(x)=\frac{1}{1-x^p} \]

斐波那契数列 \(0,1,1,2,3,5,8,13,\cdots\)，满足 \((x+x^2)F(x)+x=F(x)\)，因此其封闭形式为

\[ F(x)=\frac{x}{1-x-x^2} \]

P4451 [国家集训队] 整数的lqp拆分

给定正整数 \(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)\)，那么有

\[ \begin{cases} g_i=1,&i=0\\ g_i=\sum_{j=1}^{i}g_{i-j}f_j,&i>0 \end{cases} \]

因此 \(G(x)=G(x)F(x)+1\)，因此

\[ G(x)=\frac{1}{1-F(x)} \]

因此

\[ G(x)=\frac{1}{1-\frac{x}{1-x-x^2}}=\frac{1-x-x^2}{1-2x-x^2}=\frac{x^2+x-1}{x^2+2x-1}=1-\frac{x}{x^2+2x-1} \]

\(g\) 是一个常系数齐次线性递推，考虑如何求出 \(g\) 的通项公式。先写出递推式：

\[ g_n=2g_{n-1}+g_{n-2}~\text{ for }n\ge 2 \]

解出特征根 \(x_1=\frac{1+\sqrt 2}{2},x_2=\frac{1-\sqrt 2}{2}\)，代入初值

\[ g_0=0\\ g_1=1\\ \]

解得通项公式为

\[ g_n=\frac{2-\sqrt 2}{4}(1+\sqrt 2)^n+\frac{2+\sqrt 2}{4}(1-\sqrt 2)^n \]

\(2\) 在模 \(10^9+7\) 下有二次剩余，直接本地跑出来即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int s = 59713600;
const int i4 = 250000002;
const int A = (2 - s + MOD) * i4 % MOD;
const int B = (2 + s) * i4 % MOD;
const int a = 1 + s;
const int b = MOD + 1 - s;

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 << (A * a % MOD * qpow(a, n) % MOD + B * b % MOD * qpow(b, n) % MOD) % MOD << endl;

    return 0;
}

P4931 [MtOI2018] 情侣？给我烧了！（加强版）

有 \(n\) 对情侣来到电影院观看电影。在电影院，恰好留有 \(n\) 排座位，每排包含 \(2\) 个座位，共 \(2n\) 个座位。

现在，每个人将会随机坐在某一个位置上，且恰好将这 \(2n\) 个座位坐满。问恰好有 \(k\) 对情侣坐在同一排的方案数。

\(T\le 2\times 10^5,~n\le 5\times 10^6\)

答案可以写成

\[ \binom{n}{k}^22^kk!D_{n-k} \]

其中 \(D_n\) 表示 \(n\) 对情侣恰好 \(0\) 对和睦的方案数。考虑容斥，\(D_n\) 可以写成

\[ D_n=\sum_{k=0}^{n}(-1)^k\binom{n}{k}^22^kk!(2n-2k)! \]

仍然不好计算（递推式也不好直接看出来），考虑把组合数拆开：

\[ D_n=\sum_{k=0}\frac{(n!)^2}{(n-k)!^2k!}(2n-2k)!(-2)^k \]

然后把和 \(k\) 有关的以及和 \(n-k\) 有关的分离开，写成卷积的形式：

\[ D_n=(n!)^2\times[x^n]\biggl(\Bigl(\sum_{i=0}\frac{(-2x)^i}{i!}\Big)\Bigl(\sum_{i=0}\frac{(2i)!}{(i!)^2}x^i\Big)\bigg) \]

注意到

\[ \sum_{i=0}\frac{(-2x)^i}{i!}=e^{-2x}\\ \sum_{i=0}\frac{(2i)!}{(i!)^2}x^i=\sum_{i=0}\binom{2i}{i}x^i=\frac{1}{\sqrt{1-4x}} \]

设

\[ F(x)=\frac{e^{-2x}}{\sqrt{1-4x}} \]

考虑如何求出 \([x^n]F(x)\) 的递推式。求导：

\[ F'(x)=\frac{8xe^{-2x}}{(1-4x)^{3/2}}=\frac{8x}{1-4x}F(x) \]

即 \((1-4x)F'(x)=8xF(x)\)，考虑第 \(n\) 次项系数，得到 \((n+1)f_{n+1}-4nf_n=8f_{n-1}\)，直接递推即可，记得乘以 \((n!)^2\)。