多项式加减乘法
[h1(x)=sumlimits_{i=0}^{n1-1}h_{1i}cdot x^i; forall i ge n1, h1_{i} = 0.\
h2(x)=sumlimits_{i=0}^{n2-1}h_{2i}cdot x^i; forall i ge n2, h2_{i} = 0.\
]
加减法是对应项系数加减法
[n=max(n1,n2),f(x)=(h1+h2)(x)=sumlimits_{i=0}^{n-1}(h1_{i}+h2_{i}) cdot x^i\
n=max(n1,n2),f(x)=(h1-h2)(x)=sumlimits_{i=0}^{n-1}(h1_{i}-h2_{i}) cdot x^i\
]
乘法是卷积。
[n=n1+n2-1,f(x)=(h1+h2)(x)=sumlimits_{i=0}^{n-1}sumlimits_{j=0}^{i}(h1_{j}+h2_{i-j}) cdot x^i\
]
多项式求逆
多项式求导 | 积分
下面的求导仅局限于 (f(x)) 是一个至多 (n-1) 次的多项式。
[f(x)=sumlimits_{i=0}^{n-1}f_icdot x^i\
f'(x)=sumlimits_{i=0}^{n-2}f_{i+1}cdot {(i+1)} cdot x^i\
]
下面的积分仅局限于 (f(x)) 是一个至多 (n-1) 次的多项式。且积分结果是模 (x^n) 意义下的。
[f(x)=sumlimits_{i=0}^{n-1}f_icdot x^i\
int f(x)=C+sumlimits_{i=1}^{n-1}frac{f_{i-1}}{i} cdot x^i\
]
一般不会单独使用，只在多项式对数时使用。
多项式对数
求多项式的对数，由其定义要求常数项为1。
求 (ln f(x)) 的值，求导之后再不定积分就得到原本的值，即
[ln f(x)=int (ln f(x))'=int frac{f(x)'}{f(x)}
]
这里要求 (f(x)) 的逆，是 (O(nlog n)) 的，求导和积分都是 (O(n)) 的。
总复杂度 (O(nlog n))
多项式指数
分治FFT法。
(O(nlog ^2n))
多项式快速幂
https://www.luogu.com.cn/problem/P5245
[h(x)=sumlimits_{i=0}^{n-1}h_icdot x^i\
]
求
[f(x)=(h(x))^k\
]
当 (h_0=1) 时，可以使用多项式对数进行加速。
[ln (h(x)^k)=k ln h(x)\
f(x)=e^{ln f(x)}=e^{k ln h(x)}\
]
这里的k对 (MOD) 取模的，大概是因为他是直接作用于log吧。
当 (h_0 e 0) 时，记 (H(x)=frac{h(x)}{h_0}=sumlimits_{i=0}^{n-1}frac{h_i}{h_0}x^i)
[f(x)=e^{ln f(x)}=e^{k ln h(x)}=e^{k (ln {H(x)} + ln h_0)}\
=e^{k ln {H(x)} + kln h_0}\
=e^{k ln {H(x)}}cdot e^ {kln h_0}\
=e^{k ln {H(x)}}cdot e^ {ln (h_0)^k}\
=e^{k ln {H(x)}}cdot (h_0)^k\
]
这里第一个k是要对MOD取模（先作用于log），第二个k是要对 (varphi(MOD)) 取模（原本是指数）。
模板
这个模板把多项式传进去，然后传入多项式的原始长度（也就是，项数，a[0]...a[n-1]共n项）。会自动扩展成2的幂然后丢到FNTT转换，输出的时候只使用前n项即可（假如是模 x^n 意义的话，a[n]之后就是0了）。