哑演算初探

也不知道学不学的会 # 啥是哑演算 参考文献：[EI:哑演算初探](https://blog.csdn.net/EI_Captain/article/details/118317406) 主要思想：用形式幂 $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)$。