浅谈母函数
母函数真是迷人…… 定义 母函数是一个 无穷级数 ： G ( x ) = g 0 + g 1 x + g 2 x 2 + ⋯ = ∞ ∑ i = 0 g i x i G ( x ) = g 0 + g 1 x + g 2 x 2 + ⋯ = ∑ i = 0 ∞ g i x i 我们把系数 g 0 , g 1 ⋯ g 0 , g 1 ⋯ 提取出来，这个系数序列与母函数存在 一一对应 的关系，存在双射： → g ↔ G ( x ) g → ↔ G ( x ) . 举个例子，有母函数 G ( x ) = 1 + x + x 2 + x 3 ⋯ G ( x ) = 1 + x + x 2 + x 3 ⋯ ，则与之对应的系数表达就是 < 1 , 1 , 1 , 1 ⋯ > < 1 , 1 , 1 , 1 ⋯ > . 基本运算 加减 F ( x ) + G ( x ) ↔ < f 0 + g 0 , f 1 + g 1 , f 2 + g 2 ⋯ > F ( x ) + G ( x ) ↔< f 0 + g 0 , f 1 + g 1 , f 2 + g 2 ⋯ > F ( x ) − G ( x ) ↔ < f 0 − g 0 , f 1 − g 1 , f 2 − g 2 ⋯ > F ( x ) − G ( x ) ↔< f 0 − g 0 , f 1 − g 1 , f 2 − g 2 ⋯ > 数乘 c ∗ G ( x ) ↔ < c ∗ g 0 , c ∗ g 1 , c ∗ g 2 ⋯ > c ∗ G ( x ) ↔< c ∗ g 0 , c ∗ g 1 , c ∗ g 2 ⋯ > 乘幂 x k ∗ G ( x ) ↔ < 0 , 0 ⋯ , 0 , g 0 , g 1 ⋯ > x k ∗ G ( x ) ↔< 0 , 0 ⋯ , 0 , g 0 , g 1 ⋯ > （前面放上 k k 个 0 0 ） 卷积 F ( x ) × G ( x ) F ( x ) × G ( x ) ，跑FFT做多项式乘法即可。 用处 这里介绍最简单的用途。 你有一些水果，只能拿 3的倍数 个苹果，只能拿 ...