哑演算（入门）学习笔记-526互联

前言

本文采用 BY-NC-SA 协议发布。

这是一篇问答风格的学习笔记。

作者约等于民科，如果发现本文有错误或建议修改请告诉我。

正文

例题：定义多项式 \(F_n(x)=\sum\limits_{k=0}^n \dbinom nk A[n-k]x^k\)，求证 \(F_n(x+y)=\sum\limits_{k=0}^n \dbinom nk F_{n-k}(y) x^k\).

Alice：观察 \(F_n(x)\) 的定义，有没有一点熟悉的感觉？

Bob：长得像卷积/生成函数一类的东西...？

Alice：那中间那个组合数呢？

Bob：二项式定理！如果 \(A[n-k]\) 是幂一类的东西就能化简了。

Alice：那怎么凭空造出一个“幂”呢？

Bob：可以类似 FFT，把 \(A\) 先变成某个幂的形式，最后再变回来。

Alice：具体怎么实现？

Bob：直接用 \(\omega_n^k\) 代替 \(A[k]\) 就行了，反正最后在程序里也是用数组表达的多项式，乘一个 \(A\) 并不困难。

Alice：接下来怎么化简？

Bob：

\[\begin{aligned} F_n(x) &=\sum\limits_{k=0}^n \dbinom nk \omega_n^{n-k}x^k \\ F_n(x) &= (\omega_n+x)^n \\ F_n(x+y) &= (\omega_n+x+y)^n \\ F_n(x+y) &= \sum\limits_{k=0}^n \dbinom nk x^k (\omega_n+x)^{n-k} \end{aligned}\]

...化不下去了。

Alice：为什么化不下去？

Bob：单位根次数与 \((\omega_n+x)\) 的次数不同...等等，我全程都没用到单位根的性质！用 \(z^k\) 就行了。

\[\begin{aligned} F_n(x) &= (z+x)^k \\ F_n(x+y) &= \sum\limits_{k=0}^{n} \dbinom nk x^k (z+y)^{n-k} \\ F_n(x+y) &= \sum\limits_{k=0}^n \dbinom nk F_{n-k}(y)x^k \end{aligned}\]

Bob：好神奇...这就是哑演算吗？

Alice：大体相同，但可能还有一些 Bug。放一道例题：\(a_1=\dfrac{1}{3}\)，\(a_{n+1}=\dfrac{a_n}{3a_n+1}\)，求 \(a_n\)。

Bob：令 \(z^n=a_n\)。

\[\begin{aligned} z^{n+1} &= \dfrac{z^n}{3z^n+1} \\ 3z^{2n+1}+z^{n+1}-z^n &= 0 \\ 3a_{2n+1}+a_{n+1}-a_n &= 0 \end{aligned}\]

Bob：用正常的解法，\(a_n\) 应该等于 \(\dfrac{1}{3n}\)，不满足上式，哪错了呢？

Alice：\(z^u z^v=z^{u+v}\)，是否也有 \(a_u a_v=a_{u+v}\)？

Bob：显然没有。那就把 \(z^n\) 塞进函数里，用函数限制运算。令线性泛函 \(L\) 满足 \(L(z^k)=A[k]\)，则有 \(L(u)+L(v)=L(u+v)\)，但 \(L(u)L(v)\) 不能化成一个 \(L\) 的形式。

Alice：差不多就是这样了。