哑演算初探
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)。