「普通型生成函数」学习笔记

我太弱了,指数型没看,求导也不是很熟练,所以推式子大部分都是套公式……
不过足矣。

我从四次元菊花里抽出来一个无限数列 aa,我们定义它的生成函数 G(x)=i=0aixiG(x) = \sum\limits_{i = 0}^{\infty} a_i x^i
然后我们假装这个 xx 是没有意义的,只是一个形式,并且叫这种式子形式幂级数
但是它有什么用吗?
可以拿来练习 FFT 和 NTT

现在我们有一个方程 x1+x2+x3=20x_1 + x_2 + x_3 = 20,求它的非负整数解的个数。
显然可以插板法得到 (222)\dbinom{22}{2},但是我们假装不会插板法(

我们考虑把三个未知数的可能的解分别表示成数列 a1,a2,a3a_1,a_2,a_3
具体地说,就是让 a1,ia_{1,i} 表示第一个未知数取值 ii 的方案数,另两个类似。
即令 (因为除了要不大于 2020 以外没有别的限制,并且这个限制我们也不用管)。
然后对三个序列构造生成函数 G1(x)=G2(x)=G3(x)=11xG_1(x) = G_2(x) = G_3(x) = \dfrac 1 {1 - x}(此处根据等比数列求和公式,并且 x(1,1)x \in (-1,1)limixi=0\lim\limits_{i \to \infty} x^i = 0)……
看到这里还是感觉没什么用啊……

然后呢,我们把三个生成函数乘起来,然后看一看 x20x^{20} 项的系数……
诶,这不就是答案?
其实多项式乘法的过程,就像是背包,分别枚举三个解,所以答案就出来了。


好的,然后我们来看一道用捆绑法 + 插板法就能解决的水题:(JZOJ 1337)

小 PP 超喜欢喝水,所以他就去买水了。

商店里有 55 种水:

  1. 商店里有无数瓶;
  2. 商店里只有一瓶;
  3. 商店里竟然有 44 瓶;
  4. 5555 瓶一包卖的;
  5. 2222 瓶一包卖的。

好奇心极强的小 PP 想买 nn 瓶水,他想知道他有多少种买法。

n2311n \le 2^{31} - 1

转化一下,相当于求 x1+x2+x3+x4+x5=nx_1 + x_2 + x_3 + x_4 + x_5 = n 的非负整数解的个数,其中 0x21,0x34,5x4,2x50 \le x_2 \le 1,0 \le x_3 \le 4,5 | x_4,2 | x_5

我们考虑对五个未知数分别构造生成函数,有

相乘并因式分解得 1(1x)3\dfrac 1 {(1 - x)^3}
得到这个有什么用呢?
我们可以考虑从生成函数反推回数列。

这个地方求导可以算但是太麻烦了,我们考虑换个思路。
发现这个就是 (i=0xi)3(\sum\limits_{i = 0}^{\infty} x^{i})^3,考虑它的 xnx^n 项的系数。
根据插板法,其实就是 (n+22)\dbinom{n + 2} 2

然后记住一个重要的生成函数:1(1x)n=i=0(n+i1n1)xi\dfrac 1 {(1 - x)^n} = \sum\limits_{i = 0}^{\infty} \dbinom{n + i - 1}{n - 1} x^i,大部分普通型生成函数都能由它推出。


再举一个栗子:求自然数平方和,即 S(n)=i=1ni2S(n) = \sum\limits_{i = 1}^n i^2
考虑构造生成函数 G(x)=i=0S(i+1)xiG(x) = \sum\limits_{i = 0}^{\infty} S(i + 1) x^i
那么显然有 G(x)xG(x)=i=0(S(i+1)S(i))xi=i=0(i+1)2xiG(x) - xG(x) = \sum\limits_{i = 0}^{\infty} (S(i + 1) - S(i)) x^i = \sum\limits_{i = 0}^{\infty} (i + 1)^2 x^i

考虑后面这个生成函数等于什么。
观察发现 (n+1)2=(n+22)+(n+12)(n + 1)^2 = \dbinom{n + 2}{2} + \dbinom{n + 1}{2},所以根据之前那个式子,得到 G(x)=1+x(1x)4G(x) = \dfrac{1 + x}{(1 - x)^4}
于是第 nn 项的系数为 (n+33)+(n+23)\dbinom{n + 3}{3} + \dbinom{n + 2}{3}
由于前面做了移位,所以 S(n)=(n+23)+(n+13)S(n) = \dbinom{n + 2}{3} + \dbinom{n + 1}{3}

这个玩意也可以应用到其他常系数线性递推中去。

arknights