式子乱推

形如：给定 $m$ 次多项式 $f (k)$ ，求 $\sum_{k = 0}^{n} f (k) \times \dots$ 。 $m$ 较小 $n$ 极大。

求 $\sum f (k) x^{k} (k n)$ 。

普通幂转下降幂： $x^{n} = \sum_{i = 0}^{n} {i n} x^{\underline{i}}$ 。 $f (k) = \sum_{i = 0}^{m} b_{i} k^{\underline{i}}$ 。

下降幂乘组合数： $(k n) \times k^{\underline{m}} = (k - m n - m) n^{\underline{i}}$ 。

$= \sum_{i = 0}^{m} b_{i} n^{\underline{i}} \sum_{k = 0}^{n} (k - i n - i) x^{k}$

枚举 $k - i$ ，提出 $x^{i}$ ，二项式定理。

$= \sum_{i = 0}^{m} b_{i} n^{\underline{i}} \sum_{k = 0}^{n - i} (k n - i) x^{k + i}$

$= \sum_{i = 0}^{m} b_{i} n^{\underline{i}} x^{i} (x + 1)^{n - i}$

求 $\sum_{k = 0}^{n} f (k) (x n , k)^{k} (1 - x)^{n - k}$ 。 $f (k)$ 是 $m$ 次多项式，给出 $f_{0}, \dots, f_{m}$ 的点值表示。

二项式反演，设 $f_{x} = \sum_{i = 0}^{x} (i x) g_{i}$ ，则 $g_{x} = \sum_{i = 0}^{x} (- 1)^{x - i} (i x) f_{x}$ 。卷积。

$= \sum_{i = 0}^{m} g_{i} \sum_{k = 0}^{n} (i k) (k n) x^{k} (1 - x)^{n - k}$ 。

组合恒等式，枚举 $k - i$ ，提出 $x^{i}$ ，二项式定理。

$= \sum_{i = 0}^{m} g_{i} (i n) \sum_{k = 0}^{n} (k - i n - i) x^{k} (1 - x)^{n - k}$

$= \sum_{i = 0}^{m} g_{i} (i n) x^{i}$

Quartz 4