哑演算初探 更新于 2026/6/29 16:13:06 作者

command_block

也不知道学不学的会

啥是哑演算

参考文献：EI:哑演算初探

主要思想：用形式幂 $z^n$ 代替数列的项 $A[n]$ 进行推导。

发明这玩意的估计是幂级数单推人，什么数列都想 cos 成幂函数。

例1：线性递推

数列 $F[n]$ 有递推公式 $F[n+k]=\sum_{i=0}^{k-1}C[i]F[n+i]$ 。

给出 $C[0\sim k-1],F[0\sim k-1]$ ，快速求解 $F[n]$ 的值。

---

假设有泛函 ${\mathbb L}(\_)$ ，这是一个函数，括号里面可以填写实数、复数甚至形式幂级数。

我们将数列 $F$ 塞进 ${\mathbb L}$ 里面，引入形式元 $z$ ，令 ${\mathbb L}(z^k)=F[k]$ 。现在 ${\mathbb L}$ 中包含了 $F$ 的信息。

令这个函数满足线性性，即：

• 对于任意的 $A,B$ （可能是形式幂级数） ，都有 ${\mathbb L}(A+B)={\mathbb L}(A)+{\mathbb L}(B)$ 。

• 对于任意实数 $t$ ，有 $t{\mathbb L}(A)={\mathbb L}(tA)$ 。（注意，此处 $t$ 不能为关于 $z$ 的形式幂级数）

将递推式用 ${\mathbb L}$ 转写：

$$\begin{aligned} F[n+k]&=\sum_{i=0}^{k-1}C[i]F[n+i]\\ {\mathbb L}(z^{n+k})&=\sum_{i=0}^{k-1}C[i]{\mathbb L}(z^{n+i}) \end{aligned}$$

根据线性性，整理得

$${\mathbb L}\bigg(z^{n+k}-\sum_{i=0}^{k-1}C[i]z^{n+i}\bigg)=0={\mathbb L}(0)$$

为了方便，记 $A\xlongequal{{\mathbb L}}B$ 当且仅当 ${\mathbb L}(A)={\mathbb L}(B)$ 。

根据 ${\mathbb L}$ 的线性性，$\xlongequal{{\mathbb L}}$ 连接的“等式”可以（左右两侧同时）加减形式幂级数，或乘除实数，但不能乘除关于 $z$ 的形式幂级数。

上式简写为

$$z^{n+k}-\sum_{i=0}^{k-1}C[i]z^{n+i}\xlongequal{{\mathbb L}}0$$

记 $P(z)=z^k-\sum_{i=0}^{k-1}C[i]z^i$ （恰好是特征多项式）则 $z^nP(z)\xlongequal{{\mathbb L}} 0\ (n\in \rm N)$。

于是我们知道，对于任意 $A(z)$ ，$A(z)P(z)\xlongequal{{\mathbb L}}0$ ，这相当于多项式取模，于是

$$\begin{aligned} A(z)&\xlongequal{{\mathbb L}} B(z)\\ A(z)&\equiv B(z)\pmod{P(z)} \end{aligned}$$

二者等价。

考虑我们要求的 $F[n]={\mathbb L}(z^n)$ ，只需计算 $A(z)=z^n\bmod P(z)$ ，$A$ 只有系数 $A[0\sim k-1]$ ，则

$$\begin{aligned} z^n&\equiv A(z)\pmod{P(z)}\\ z^n&\xlongequal{{\mathbb L}}A(z)\\ L(z^n)&=\sum_{i=0}^{k-1}A[i]L(z^i)\\ F[n]&=\sum_{i=0}^{k-1}A[i]F[i] \end{aligned}$$

推导完毕。计算时，只需倍增求解 $A(z)=z^n\bmod P(z)$，FFT 可做到 $O(k\log k\log n)$ 。

不难发现这和市面上流传的常系数线性递推算法等价。

例2

假设我们有无穷数列 $A[n]$，定义多项式

$$F_n(x)=\sum_{k=0}^n\dbinom{n}{k}A[n-k]x^k$$

证明：

$$F_n(x+y)=\sum_{k=0}^n\dbinom{n}{k}F_{n-k}(y)x^k$$

---

令 ${\mathbb L}$ 满足线性性且 ${\mathbb L}(z^k)=A[k]$ 。则条件转写为

$$\begin{aligned} F_n(x)&=\sum_{k=0}^n\dbinom{n}{k}{\mathbb L}(z^{n-k})x^k\\ &={\mathbb L}\bigg(\sum_{k=0}^n\dbinom{n}{k}z^{n-k}x^k\bigg)\\ &={\mathbb L}\big((z+x)^n\big) \end{aligned}$$

用上式代换可得

$$\begin{aligned} \sum_{k=0}^n\dbinom{n}{k}F_{n-k}(y)x^k&=\sum_{k=0}^n\dbinom{n}{k}{\mathbb L}\big((z+y)^n\big)x^k\\ &={\mathbb L}\bigg(\sum_{k=0}^n\dbinom{n}{k}(z+y)^{n-k}x^k\bigg)\\ &={\mathbb L}\big((z+y+x)^n\big)\\ &=F_n(x+y) \end{aligned}$$

例3

给出 $n,p,q,A[0\sim n]$ ，对于 $k=0\sim n$ ，分别求

$$\sum_{a=0}^k\sum_{b=0}^{n-k}\dbinom{k}{a}\dbinom{n-k}{b}A[a+b]p^aq^b$$

答案对 $998244353$ 取模。

---

令 ${\mathbb L}$ 满足线性性且 ${\mathbb L}(z^k)=A[k]$ 。则

$$\begin{aligned} {\rm Ans}[k]=&\sum_{a=0}^k\sum_{b=0}^{n-k}\dbinom{k}{a}\dbinom{n-k}{b}A[a+b]p^aq^b\\ =&{\mathbb L}\Bigg(\sum_{a=0}^k\sum_{b=0}^{n-k}\dbinom{k}{a}\dbinom{n-k}{b}z^{a+b}p^aq^b\Bigg)\\ =&{\mathbb L}\Big((1+pu)^k(1+qu)^{n-k}\Big)\\ \end{aligned}$$

记 $T_k(u)=(1+pu)^k(1+qu)^{n-k}$ ，则

$$\begin{aligned} {\rm Ans}[k]&={\mathbb L}\Bigg(\sum_{i=0}^nT_k[i]z^i\Bigg)\\ &=\sum_{i=0}^nT_k[i]A[i] \end{aligned}$$

显然这是个线性算法，将其转置得到对偶算法

$${\rm Ans}[k]=\sum_{i=0}^nT_i[k]A[i]$$

注意 $\rm Ans$ 和 $T_i$ 的系数对齐了，记 $S(u)=\sum_{k=0}^n{\rm Ans}[i]u^i$ ，则

$$\begin{aligned} S(u)&=\sum_{i=0}^nA[i]T_i(u)\\ &=\sum_{i=0}^nA[i](1+pu)^k(1+qu)^{n-k}\\ &=(1+qu)^n\sum_{i=0}^nA[i]\Big(\frac{1+pu}{1-qu}\Big)^k\\ &=(1+qu)^nA\Big(\frac{1+pu}{1-qu}\Big) \end{aligned}$$

众所周知，复合一次分式可以卷积计算。将这个算法转置，复杂度 $O(n\log n)$。