25.5.12 闲话 2：EGF 运算
喵仔牛奶
·
·
算法·理论
对 n 次 EGF 求逆、求 exp、求 ln、求 k 次幂。模数不一定是质数。
可以发现对于一个 EGF F(x)，[\frac{x^n}{n!}]F'(x)=[\frac{x^{n+1}}{(n+1)!}]F'(x)。
求逆
设 G(x)=F^{-1}(x)，那么 F(x)G(x)=1。考察 \frac{x^n}{n!} 这项（n\ge 1）：
n!\sum_{i=0}^{n}\frac{f_{i}}{i!}\frac{g_{n-i}}{(n-i)!}=0
\sum_{i=0}^{n}\binom{n}{i}f_{i}g_{n-i}=0
g_{i}=-\frac{1}{f_0}\sum_{j=1}^{i}\binom{i}{j}f_{j}g_{i-j}
如果 f_0 有逆则可以求。
求 exp
设 G(x)=\exp F(x)，那么 G'(x)=G(x)F'(x)。考察 \frac{x^n}{n!} 这项：
\frac{g_{n+1}}{n!}=\sum_{i=0}^{n}\frac{f_{i+1}}{i!}\frac{g_{n-i}}{(n-i)!}
g_{n+1}=\sum_{i=0}^{n}\binom{n}{i}f_{i+1}g_{n-i}
g_{i}=\sum_{j=1}^{i}\binom{i-1}{j-1}f_{j}g_{i-j}
求 ln
设 G(x)=\ln F(x)，那么 G'(x)F(x)=F'(x)。考察 \frac{x^n}{n!} 这项：
\frac{f_{n+1}}{n!}=\sum_{i=0}^{n}\frac{g_{i+1}}{i!}\frac{f_{n-i}}{(n-i)!}
g_{n+1}f_{0}=f_{n+1}-\sum_{i=0}^{n-1}\binom{n}{i}g_{i+1}f_{n-i}
g_{i}=f_i-\sum_{j=1}^{i-1}\binom{i-1}{j-1}g_{j}f_{i-j}
最后一步 f_0 消失是因为求 ln 要保证 f_0=1。
求 k 次幂
设 G(x)=F^k(x)，那么 G'(x)F(x)=kF'(x)G(x)。考察 \frac{x^n}{n!} 这项：
n!\sum_{i=0}^{n}\frac{g_{i+1}}{i!}\frac{f_{n-i}}{(n-i)!}=n!k\sum_{i=0}^{n}\frac{f_{i+1}}{i!}\frac{g_{n-i}}{(n-i)!}
\sum_{i=0}^{n}\binom{n}{i}g_{i+1}f_{n-i}=k\sum_{i=0}^{n}\binom{n}{i}f_{i+1}g_{n-i}
\binom{n}{n}f_0g_{n+1}=k\sum_{i=0}^{n}\binom{n}{i}f_{i+1}g_{n-i}-\sum_{i=0}^{n-1}\binom{n}{i}g_{i+1}f_{n-i}
g_{i}=\frac{1}{f_0}\left(k\sum_{j=1}^{i}\binom{i-1}{j-1}f_{j}g_{i-j}-\sum_{j=1}^{i-1}\binom{i-1}{j-1}g_{j}f_{i-j}\right)
如果 f_0 有逆则可以求。