多项式补完计划
退役前给自己看的，删了一些东西放出来了，有兴趣可以看看
FFT，NTT全世界都会了…
分治FFT
是一类思想。举个板子： 给出了$g_{1,…,n-1}$，求$f_{0,…,n-1}$ $$f_i = \sum_{j=1}^i f_{i-j} g_j$$ 计算$f$需要用到之前的$f$。所以考虑像CDQ一样的做，用 左半部分贡献右半部分。 对于右半边的点$x$，左边有贡献： $$w_x = \sum_{i=l}^{mid} f_i g_{x - i}$$ 这个东西可以FFT做出来。
多项式求逆
倍增求解。假设已经求出了模$\lceil \frac{x}{2} \rceil$的解$f_0^{-1}(x)$ $$f(x)f^{-1}(x) \equiv f(x)f_0^{-1}(x)\pmod {\lceil \frac{x}{2} \rceil}$$ $$f^{-1}(x) - f_0^{-1}(x) \equiv 0 \pmod {\lceil \frac{x}{2} \rceil}$$ 平方，移项 $$f^{-1}(x) \equiv (2 - f(x)f_0^{-1}(x)) f_0^{-1}(x) \pmod {x^n}$$ $O(nlogn)$
多项式除法
已知次数为$n,m$的$F(x),G(x)$，求 $$F(x) = Q(x)G(x) + R(x)$$ 我们考虑反转一个多项式的系数，可以发现就是 $$A_R(x) = x^n A(\frac{1}{x})$$ 那么利用反转化简 $$x^n F(\frac{1}{x}) = x^{n-m} Q(\frac{1}{x}) x^mG(\frac{1}{x}) + x^{n-m+1} x^{m-1}R(\frac{1}{x})$$ $$F_R(x) \equiv Q_R(x)G_R(x) + x^{n-m+1}R_R(x) \pmod {x^{n-m+1}}$$ $$Q_R(x) \equiv F_R(x)G_R^{-1}(x)\pmod {x^{n-m+1}}$$ 于是可以求解$Q_R(x)$，然后求出$Q(x),R(x)$。$O(nlogn)$
多项式求导与积分
$$f(x) = \sum_{i=0}^n a_ix^i$$ $$f^{‘}(x) = \sum_{i=0}^{n-1}(i+1)a_{i+1}x^i$$ $$\int_{1}^n a_i x^i = \sum_{i=1}^{n+1}\frac{a_{i-1}x^i}{i}$$
多项式泰勒展开
$$g(x) = \sum_{i=0}^{+ \infty} \frac{f^{(i)} (x_0) }{i!} (x - x_0)^i$$
多项式牛顿迭代
$$g(f(x)) \equiv 0 \pmod{x^n}$$ 已知$g(x)$，求$f(x)$ 一个神奇的东西。其实有了她多项式这些问题都可以随便做啦～。 倍增求解。假装已经求出了$f_0(x)$，满足： $$g(f_0(x)) \equiv 0 \pmod{ x^{\lceil \frac{n}{2} \rceil} }$$ 那么在$f_0(x)$泰勒展开 $$\sum_{i=0}^{+ \infty} \frac{g^{(i)}(f_0(x))}{i!}(f(x)-f_0(x))^i \equiv 0 \pmod{x^n} $$ 因为 $$\forall i \geq 2, (f(x) - f_0(x))^i \equiv 0 \pmod{x^n}$$ 所以可以化简得到 $$g(f_0(x)) + g^{‘} (f_0(x))(f(x) - f_0(x)) \equiv 0 \pmod{x^n}$$ $$f(x) \equiv f_0(x) - \frac{g(f_0(x))}{g^{‘}(f_0(x))} \pmod{x^n}$$
多项式ln
定义多项式的对数函数为其与麦克劳林级数的复合，即 $$\ln (1 - F(x)) = - \sum_{i=1}^{\infty} \frac{F^{(i)}(x)}{i} $$ 我们令$F(x)=ln(x)$ $$G(x)=F(A(x))$$ $$G^{‘} (x) = F^{‘} (A(x)) A^{‘} (x) = \frac{A^{‘} (x)}{A(x)}$$ 求导求逆求积分。$O(nlogn)$
多项式exp
同样定义多项式的对数函数为其与麦克劳林级数的复合，即 $$\exp F(x) = \sum_{i=0}^{\infty} \frac{F^{(i)}(x)}{i!}$$ $$F(x) \equiv e^{A(x)} \pmod{x^n}$$ $$\ln F(x) \equiv A(x) \pmod{x^n}$$ $$\ln F(x) - A(x) \equiv 0 \pmod{x^n}$$ 那么考虑令 $$G(F(x)) \equiv \ln F(x) - A(x) \pmod{x^n} $$ 因为$G(F(x)) \equiv 0$，可以把$A(x)$看作常数项，于是很好求导 $$G^{‘}(F(x)) \equiv \frac{1}{F(x)} \pmod{x^n}$$ 用牛顿迭代可知 $$F(x) \equiv F_0(x)(1 - \ln F_0(x) + A(x)) \pmod {x^n}$$ $O(nlogn)$
多项式开根
会颓exp的式子之后，这个很naive。 $$F(x) \equiv \frac{A(x)}{2F_0(x)} + \frac{F_0(x)}{2} \pmod{x^n}$$ $O(nlogn)$
多项式快速幂
倍增可以，但是有点慢 $$A^k(x) \equiv \exp(k \ln A(x))$$ $O(nlogn)$ 关于多点求值插值什么的：懒得学，盲猜省选NOI不会考，咕咕（FLAG）
任意模数NTT
直接用MTT。考虑把数字拆成$xM+y$，其中$M$是一个界限，取$2^{15}-1$ 那么直接考虑FFT，需要$9$次。 主要问题是有一个优化技巧：一次FFT做两个DFT 具体来说就是$P(x)=A(x)+iB(x),Q(x)=conj(P(x))$ 那么对$P$FFT之后，$Q(x)=conj(P(j)),j = (lim-i) \mod lim$ 则$DFT(A) = \frac{P+Q}{2},DFT(B)=-i\frac{P-Q}{2}$ 对于MTT的DFT部分，直接套这个Trick就行了。那么可以得出来$xy$的四个积。 但是IDFT的时候，两个数都是实部虚部都不为0，好像有点问题的样子。。 其实这个问题很好解决（虽然想了很久。。）：令$F=A+Bi$，其中$A,B$都是点值表示，因为两个多项式$A,B$的系数表示都是只有实部不为$0$，那么仔细想一想可以发现，直接把$F$做IDFT就可以还原出来$A,B$，一个在实部一个在虚部。可以理解为，因为它们都是只有一个部有数，分别放在实虚部分，它们是互不影响的。
迷惑斯特林数系列
第二类行
最简单的一个。。 $$n^m = \sum_{i=0}^m {m \brace i} \binom{n}{i} i!$$ 可以发现，把$\sum$扩展到$n$也是没有问题的 $$n^m = \sum_{i=0}^n {m \brace i} \binom{n}{i} i!$$ $${m \brace n} = \frac{1}{n!} \sum_{i=0}^n \binom{n}{i} (-1)^{n-i} i^m$$ 化简一下就是卷积 $O(nlogn)$
第一类行
有一个貌似能归纳证明的式子 $$\sum_{i=0}^n{n \brack i}x^i = x^{\overline n}$$ 那么倍增求就行了，手动玩一下二项式。$O(nlogn)$
第二类列
把列写成OEF，考虑递推式，可以整理得到 $$x^m(\prod_{i=1}^m (1-ix))^{-1}$$ 那么分治NTT就行了，$O(nlog^2n)$
第一类列
考虑组合意义，$n$个数，由$m$个轮换组成。那么构造轮换EGF（因为有标号），再除掉排列数 $${ n \brack m } = \frac{n!}{m!} [x^n](\sum_{i=1} (i-1)! \frac{x^i}{i!})^m$$ 不是很懂非1的ln，倍增完事$O(nlog^2n)$
一类$O(n^2)$的多项式技巧：以exp为例，看这里https://baka.online/noi-online3%e4%bc%98%e7%a7%80%e5%ad%90%e5%ba%8f%e5%88%97-%e9%9b%86%e5%90%88%e5%b9%82%e7%ba%a7%e6%95%b0exp/ 剩下的更简单，模仿一下就有了
迁移到Hexo后的Update：站内搜索《NOI Online#3优秀子序列 集合幂级数exp》
奇怪的题目：
付公主的背包
付公主的背包 首先显然构造函数$f_i(x) = \frac{1}{1 - x^{v_i}}$卷起来就行了。但是这个复杂度很高。 考虑用加法代替乘法，求个$\ln $就可以了。这题的$\ln$有极好的性质： $$G(x) = \ln F(x) = \ln \frac{1}{1 - x^v}$$ 考虑求导求积分化简式子： $$G^{‘}(x) = \frac{F^{‘}(x)}{F(x)} = \sum_{i=1}^{\infty} v x^{xi - 1} $$ $$G(x) = \sum_{i=1}^{\infty} \frac{1}{i} x^{vi} $$ 记录每种$v$有几个，暴力求系数，调和级数的复杂度，再敲个多项式$\exp$就行了。