一类特殊的模意义下的多项式微分方程的求解

### 引言 在一类多项式理论中，常常会遇到 $F'=H(F)$ 的形式，有时可以通过 $EGF$ 求解 但像我这种只会暴力计数的选手经常会推出一个看起来只能分治 $FFT$ 的式子，实际上一些特殊的形式可以做到更优 ### 前置技能 #### 多项式理论基础 看 **参考资料** 吧 #### 一阶线性微分方程 ##### 齐次线性方程 ###### 形式 $$\frac{dy}{dx}+P(x)y=0$$ ###### 求解 $$ \begin{aligned} & \frac{dy}{dx}+P(x)y=0 \\ \Rightarrow & \frac{dy}{y}=-P(x)dx \\ \Rightarrow & \int \frac{dy}{y}=c_1 -\int P(x)dx \\ \Rightarrow & \ln |y|=c_1- \int P(x)dx \\ \Rightarrow & y=C e^{-\int P(x)dx} \quad (C=\pm e^{c_1}) \end{aligned} $$ ##### 非齐次线性方程 ###### 形式 $$\frac{dy}{dx}+P(x)y=Q(x)$$ ###### 求解 可以通过对应的齐次线性方程，使用 **常数变易法** 求解 设 $y=u(x) e^{-\int P(x)dx}$，则： $$ \begin{aligned} & \frac{dy}{dx}=\frac{du}{dx} e^{-\int P(x)dx} - u(x)P(x) e^{-\int P(x)dx} \\ \Rightarrow & \frac{du}{dx} e^{-\int P(x)dx} - u(x)P(x) e^{-\int P(x)dx} + P(x)u(x) e^{-\int P(x)dx} =Q(x) \\ \Rightarrow & \frac{du}{dx} = Q(x) e^{\int P(x)dx} \\ \Rightarrow & \int du=C+\int Q(x) e^{\int P(x)dx} dx \\ \Rightarrow & u(x)=C+\int Q(x) e^{\int P(x)dx} dx \\ \Rightarrow & y= e^{-\int P(x)dx} \left( C + \int Q(x) e^{\int P(x)dx} dx \right) \\ \end{aligned} $$ 可以发现，等式右端第一项是对应的齐次线性方程的通解，第二项是非齐次线性方程的一个特解（在 $C=0$ 时取到） 即 **一阶非齐次线性方程的通解等于对应的齐次方程的通解与非齐次方程的一个特解之和** ### 正文 考虑一类多项式微分方程： $$F'=H(F)$$ 一般来说只需要考虑模 $x^n$ 意义下的值即可 那么考虑倍增的过程，假设现在要求 $F_{2n}$，那么可以先递归求解 $F_{n}$ 于是现在有： $$F' _ {n} \equiv H(F _ n) \pmod {x^n}$$ 考虑 $H$ 在 $F_{n}$ 处的泰勒展开，可以得到： $$F'_{2n} \equiv H(F_{2n}) \equiv H(F_n)+H'(F_n) (F_{2n}-F_{n}) \pmod {x^{2n}}$$ 整理可得： $$F'_{2n} \equiv \left( H(F_n)-H'(F_n)F_n \right) + H'(F_{n}) F_{2n} \pmod {x^{2n}}$$ 设 $y=F_{2n}$，可以得到： $$ \frac{dy}{dx}+P(x)y=Q(x) $$ 于是可以得知它的一组解是： $$y=e^{-\int P(x) d x}\left(C+\int Q(x) e^{\int P(x) d x} d x\right)$$ 也就是： $$y=e^{\int H'(F_n)dx} \left( C+ \int \left( H(F_n)-H'(F_n)F_n \right) e^{- \int H'(F_n)dx} \right)$$ ### 例题 #### 例1 ~~这道题可能跟上面没啥关系~~ ##### 题目描述 求有多少个 $1 \sim n$ 的排列，使得环的大小都在 $A$ 中 其中 $1 \le n \le 10^5, 0 \le k \le n, 1 \le a_i \le n$ #### 题解 设 $f_n$ 表示答案，则有： $$ f_n=\sum_{i=1}^{n} {n-1 \choose i-1} f_{n-i} (i-1)![i \in A] $$ 设 $g_i=(i-1)![i \in A]$，则有： $$ \begin{aligned} & f_n=\sum_{i=1}^{n} {n-1 \choose i-1} f_{n-i}g_{i} \\ \Rightarrow &\frac{f_n}{(n-1)!}=\sum_{i=0}^{n} \frac{f_{n-i}}{(n-i)!} \frac{g_i}{(i-1)!} \end{aligned} $$ 设 $[x^n]F(x)=\frac{f_n}{n!}$，且 $[x^n]G(x)=\frac{g_n}{(n-1)!}=[n \in A]$，则有： $$xF'(x)=F(x)G(x)$$ 设 $y=F(x)$，则有： $$y'+\frac{-G(x)}{x}y=0$$ 由于 $F(0)=1$，于是有： $$ y=C \cdot e^{-\int \frac{-G(x)}{x} dx}=e^{\int \frac{G(x)}{x}dx} $$ ### 参考资料 - [zhoutb【UOJ #50】链式反应](https://www.luogu.org/blog/zhoutb2333/uoj-50-lian-shi-fan-ying) - [czy 【多项式基础理论】](https://github.com/KingSann/useless-papers/blob/master/多项式基础理论/多项式基础理论.pdf)