浅谈多项式微分方程(更新中)

感觉杜老师写得比我好一亿倍,但是我还是想写一下这个东西加深记忆。
杜老师博客
我还不是很懂,先写一部分。

一般形式微分方程的应用

$\frac{dy}{dx}+yP(x)=0$
解法:
$dy=-yP(x)dx$
$\frac{1}{y} dy=-P(x)dx$
$\int \frac{1}{y} dy=\int -P(x)dx$
$\pm \ln y=-\int P(x) dx+C$
$y=\pm e^{-\int P(x) dx+C}$
利用这个方程可以解决一类带导数的多项式微分方程问题,可以看我的另外一篇博客。
[集训队作业2018]普通的计数题
类似的题还有$\lbrack$uoj#50$\rbrack$链式反应

一种求解幂次函数问题的方法

求一个多项式$P(x)^k \mod x^m$(设$P(x)$有n项)
令$Q(x)=P(x)^k$,两边同时求对数,有:
$\frac{Q'(x)}{Q(x)}=k\frac{P'(x)}{P(x)}$
$P(x)Q'(x)=kP'(x)Q(x)$
$\displaystyle\sum_{j=0}^{n-1} (i-j+1)p_j q_{i-j+1}=k\displaystyle\sum_{j=0}^{n-1} jp_{j}q_{i-j+1}$
直接递推可以做到复杂度$O(nm)$

Tagged with:

发表评论