2月多项式计划

## 2月多项式计划 计划每天一道多项式，并写一句话题解。 ### 2.2 Luogu P3338 [ZJOI2014]力 求 $$\forall1\le i\le n,E_i=\sum_{j=1}^{i}\frac{q_j}{(i-j)^2}-\sum_{j=i}^n\frac{q_j}{(i-j)^2}$$ 记$g_i=\frac{1}{i^2}$ $$E_i=\sum_{j=1}^{i}q_jg_{i-j}-\sum_{j=i}^nq_jg_{j-i}$$ 左边是卷积形式，右边按套路反转，记$req_j=q_{n-j}$ $$E_i=\sum_{j=1}^{i}q_jg_{i-j}-\sum_{j=0}^{n-i}req_jg_{n-i-j}$$ 两边都是卷积，FFT卷一下就做完了($E_i$就是最后多项式第$i$项系数），时间复杂度$\Theta(n\log n)$ ### 2.3 Luogu P3723 [AH2017/HNOI2017]礼物 给$x_i,y_i(y_{n+i}=y_i)$,求 $$\min_{0\le k<n,-m\le c\le m}\sum_{i=1}^n(x_i-y_{i+k}+c)^2$$ $c$拿出来，即 $$(\sum_{i=1}^nx_i^2-2x_iy_{i+k}+y_{i+k}^2)+nc^2+2c\sum_{i=1}^n(x_i-y_{i+k})$$ 右边是关于$c$的二次函数，初中知识求min即可。 左边将常数与变量分开，即 $$(\sum_{i=1}^nx_i^2)+(\sum_{i=1}^ny_i^2)-(2\sum_{i=1}^nx_iy_{i+k})$$ 左边预处理下，右边还是反转的套路，记$rex_i=x_{n-i+1}$ $$-2\sum_{i=1}^nrex_{n-i}y_{i+k}$$ 这是一个有点变形的卷积形式，用FFT计算一下，最后的最小值就是$[n,n+n-1]$中最小的系数。时间复杂度$\Theta(n\log n)$ ### 2.4 模板 多项式求逆 给多项式$F(x)$,求$G(x)$满足$F(x)*G(x)\equiv1(mod\ x^n)$,系数对998244353取模. 与NTT类似地,假设已求得$F(x)*G1(x)\equiv1(mod\ x^{n/2})$ $$F(x)*(G(x)-G1(x))\equiv0(mod\ x^{n/2})$$ $$G(x)-G1(x)\equiv0(mod\ x^{n/2})$$ 两边平方, $$G^2(x)-2GG1(x)+G1^2(x)\equiv0(mod\ x^n)$$ 同乘$F(x),$ $$G(x)-2G1(x)+F(x)G1^2(x)\equiv 0(mod\ x^n)$$ 显然最后就是$G(x)=2G1(x)-F(x)G1^2(x)$ 也就是求出了$F(x)*G1(x)\equiv1(mod\ x^{n/2})$(即一半规模的子问题)后,NTT卷一下就可得到现在的结果.显然可以递归/迭代做到. 时间复杂度: $$T(n)=T(n/2)+\Theta(n\log n)=\Theta(n\log n)$$ ### 2.5 模板 MTT（任意模数NTT） 先吐槽一下洛谷今天智推没有多项式。。。 给两个多项式$F(x),G(x)$,求$F(x)*G(x)$,系数对$p(p\le 10^9+9)$取模。 考虑最坏情况下，系数最大是$10^5*10^9*10^9=10^{23}$,`long long`也装不下，同时找不到合适的NTT模数。 有两种解决方案： 1.取三个合适的模数做NTT，然后CRT合并（究极大常数） 2.将每一项拆成$aM+b$,当$M$与$\sqrt p$同阶，让$a,b$都变为与$\sqrt p$同阶，相乘的结果用`double`就能够储存了。 令$F(x)=F1(x)M+F2(x),G(x)=G1(x)M+G2(x)$ 则 $$F(x)*G(x)=F1(x)G1(x)M^2+F1(x)G2(x)M+F2(x)G1(x)M+F2(x)G2(x)$$ 暴力FFT计算即可（需要做4次DFT，4次IDFT），时间复杂度$\Theta(n\log n)$,但常数似乎没有想象中的大，最长点255ms tip：注意FFT时单位根一路乘过去精度会挂。。应该预处理单位根。可见代码。 ### 2.6 多项式任意模数逆 把求逆的板子的NTT换成MTT就没了。 时间复杂度$\Theta(n\log n)$,有点卡常卡精度。 ### 2.7 多项式开根 给一个多项式$F(x),$求一个多项式$G(x)$满足$G(x)^2\equiv F(x)\ (mod\ x^n)$ 仍然是倍增的套路，设已求得$G1(x)^2=F(x)\ (mod\ x^{n/2})$ $$G(x)\equiv G1(x)\ (mod\ x^{n/2})$$ $$G(x)^2-2G(x)G1(x)+G1(x)^2\equiv0\ (mod\ x^{n})$$ $$G(x)\equiv\frac{F(x)-G1(x)^2}{2G1(x)}\ (mod\ x^{n})$$ 所以求逆然后NTT就能求得$G(x)$,倍增一下,就做完了。仍然卡常。~~我吸氧了，你呢~~ $$T(n)=T(n/2)+\Theta(n\log n)=\Theta(n\log n)$$ ### 2.8 Luogu P4721 【模板】分治 FFT 给序列$g_{1..n-1}$,且有$f_0=1,f_i=\sum_{j=1}^{i-1}f_jg_{i-j},$求$f_{0..n-1}\ (mod\ 998244353)$ 由于每一项依赖之前的项，因此无法直接NTT卷积（对998244353取模还FFT啥呀）。 考虑分治。左半段的结果直接递归算，右半段结果就是段内的贡献（递归算）+左半段对右半段的贡献（非常类似 $\text{CDQ}$ 分治） 考虑如何计算左半段对右半段的贡献： 将左半段与$g$卷积，结果的右半段就是对右半段的贡献。 时间复杂度$T(n)=2T(n/2)+\Theta(n\log n)=\Theta(n\log^2n)$ 另，可用生成函数证明$F(x)=\frac{1}{1-G(x)}$,用多项式求逆可在$\Theta(n\log n)$时间内解决。 ------------ 中途鸽了好久。。。多项式太难了。。。 ------------ ### 2.19 Luogu P4725 【模板】多项式ln 给多项式$F(x),$求$G(x)\equiv\ln F(x)(mod\ x^n)$,系数对$998244353$取模。 前置技能：求导，不定积分（现学现卖来得及的！） 由复合函数求导公式（$g(f(x))'=g'(f(x))f'(x)$）且$\ln'=\frac{1}{x}$得 $$G'(x)\equiv\frac{F'(x)}{F(x)}(mod\ x^n)$$ 对$F$求导，求逆，相乘得到$G'(x)$,再不定积分即可得到$G(x)$，时间复杂度$\Theta(n\log n)$ PS:默认$G(x)$常数是0