专栏文章

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

nnekko
算法·理论参与者 31已保存评论 34

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
34 条
当前快照
1 份
快照标识符
@mhz5s39z
此快照首次捕获于
2025/11/15 01:55
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文

引言

在一类多项式理论中，常常会遇到 F′=H(F)F'=H(F) 的形式，有时可以通过 EGFEGF 求解
但像我这种只会暴力计数的选手经常会推出一个看起来只能分治 FFTFFT 的式子，实际上一些特殊的形式可以做到更优

前置技能

多项式理论基础

看 参考资料 吧

一阶线性微分方程

齐次线性方程
形式
dydx+P(x)y=0\frac{dy}{dx}+P(x)y=0
求解
dydx+P(x)y=0⇒dyy=−P(x)dx⇒∫dyy=c1−∫P(x)dx⇒ln⁡∣y∣=c1−∫P(x)dx⇒y=Ce−∫P(x)dx(C=±ec1)\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}
非齐次线性方程
形式
dydx+P(x)y=Q(x)\frac{dy}{dx}+P(x)y=Q(x)
求解
可以通过对应的齐次线性方程，使用 常数变易法 求解
设 y=u(x)e−∫P(x)dxy=u(x) e^{-\int P(x)dx}，则：
dydx=dudxe−∫P(x)dx−u(x)P(x)e−∫P(x)dx⇒dudxe−∫P(x)dx−u(x)P(x)e−∫P(x)dx+P(x)u(x)e−∫P(x)dx=Q(x)⇒dudx=Q(x)e∫P(x)dx⇒∫du=C+∫Q(x)e∫P(x)dxdx⇒u(x)=C+∫Q(x)e∫P(x)dxdx⇒y=e−∫P(x)dx(C+∫Q(x)e∫P(x)dxdx)\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=0C=0 时取到）
即 一阶非齐次线性方程的通解等于对应的齐次方程的通解与非齐次方程的一个特解之和

正文

考虑一类多项式微分方程：
F′=H(F)F'=H(F)
一般来说只需要考虑模 xnx^n 意义下的值即可
那么考虑倍增的过程，假设现在要求 F2nF_{2n}，那么可以先递归求解 FnF_{n}
于是现在有：
Fn′≡H(Fn)(modxn)F' _ {n} \equiv H(F _ n) \pmod {x^n}
考虑 HH 在 FnF_{n} 处的泰勒展开，可以得到：
F2n′≡H(F2n)≡H(Fn)+H′(Fn)(F2n−Fn)(modx2n)F'_{2n} \equiv H(F_{2n}) \equiv H(F_n)+H'(F_n) (F_{2n}-F_{n}) \pmod {x^{2n}}
整理可得：
F2n′≡(H(Fn)−H′(Fn)Fn)+H′(Fn)F2n(modx2n)F'_{2n} \equiv \left( H(F_n)-H'(F_n)F_n \right) + H'(F_{n}) F_{2n} \pmod {x^{2n}}
设 y=F2ny=F_{2n}，可以得到：
dydx+P(x)y=Q(x)\frac{dy}{dx}+P(x)y=Q(x)
于是可以得知它的一组解是：
y=e−∫P(x)dx(C+∫Q(x)e∫P(x)dxdx)y=e^{-\int P(x) d x}\left(C+\int Q(x) e^{\int P(x) d x} d x\right)
也就是：
y=e∫H′(Fn)dx(C+∫(H(Fn)−H′(Fn)Fn)e−∫H′(Fn)dx)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∼n1 \sim n 的排列，使得环的大小都在 AA 中
其中 1≤n≤105,0≤k≤n,1≤ai≤n1 \le n \le 10^5, 0 \le k \le n, 1 \le a_i \le n

题解

设 fnf_n 表示答案，则有：
fn=∑i=1n(n−1i−1)fn−i(i−1)![i∈A]f_n=\sum_{i=1}^{n} {n-1 \choose i-1} f_{n-i} (i-1)![i \in A]
设 gi=(i−1)![i∈A]g_i=(i-1)![i \in A]，则有：
fn=∑i=1n(n−1i−1)fn−igi⇒fn(n−1)!=∑i=0nfn−i(n−i)!gi(i−1)!\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}
设 [xn]F(x)=fnn![x^n]F(x)=\frac{f_n}{n!}，且 [xn]G(x)=gn(n−1)!=[n∈A][x^n]G(x)=\frac{g_n}{(n-1)!}=[n \in A]，则有：
xF′(x)=F(x)G(x)xF'(x)=F(x)G(x)
设 y=F(x)y=F(x)，则有：
y′+−G(x)xy=0y'+\frac{-G(x)}{x}y=0
由于 F(0)=1F(0)=1，于是有：
y=C⋅e−∫−G(x)xdx=e∫G(x)xdxy=C \cdot e^{-\int \frac{-G(x)}{x} dx}=e^{\int \frac{G(x)}{x}dx}

参考资料

评论

共 34 条评论，欢迎与作者交流。

正在加载评论...