生成函数

杨辉三角

一个常见的套路：对于前缀和矩阵

$$A:=\left[\begin{array}{cccccc}1& 0& 0& 0& \cdots & 0\\ 1& 1& 0& 0& \cdots & 0\\ 1& 1& 1& 0& \cdots & 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 1& 1& 1& \cdots & 1\end{array}\right],$$

它去乘一个向量 $\overrightarrow{b}$ 有一个等价形式：

$$A\times \overrightarrow{b}=(1+x+x^2+\cdots )(b_0+b_{1}x+b_2{x}^2+\cdots ).$$

除此之外，矩阵幂和生成函数之间有联系。