多项式
-
多项式乘法
多项式可以相乘！
$FFT,NTT$啥的就是解决这个的……怎么证明求解就咕了
多项式可以求逆元！
对于一个多项式$f(x)$，定义它的最高项次数为这个多项式的度，即$deg$
根据逆元的定义，如果两个多项式$f(x),g(x)$满足$deg_g\le deg_f$，并且$f(x)g(x)\equiv 1(\mod x^n)$，则$g(x)$就是$f(x)$在模$x^n$下的逆元
如果知道$f(x)$，如何求解$g(x)$呢？
假设在模$x^{\left\lceil\frac{n}{2}\right\rceil}$意义下$f(x)$的逆元为$g’(x)$，则有$f(x)g’(x)\equiv 1(\mod x^{\left\lceil\frac{n}{2}\right\rceil})$
因为$g(x)$和$f(x)$在模$x_n$的意义下乘积只剩下一个常数项$1$，那么在模$x^{\left\lceil\frac{n}{2}\right\rceil}$的意义下乘积肯定也是$1$（即$g(x)$依然是$f(x)$的逆元）
有$f(x)g(x)\equiv 1(\mod x^{\left\lceil\frac{n}{2}\right\rceil})$
这个与上面模数相同了，可以相减
$f(x)(g(x)-g’(x))\equiv 0(\mod x^{\left\lceil\frac{n}{2}\right\rceil})$
同除$f(x)$，$g(x)-g’(x)\equiv 0(\mod x^{\left\lceil\frac{n}{2}\right\rceil})$
两边平方（？）
$g^2(x)+g’^2(x)-2g(x)g’(x)\equiv 0(\mod x^n)$
诶等等为什么模数也可以平方啊……
前面那个式子因为取模后为$0$，说明其在$0\sim x^{\left\lceil\frac{n}{2}\right\rceil}-1$次的系数都为$0$（只对第$x^{\left\lceil\frac{n}{2}\right\rceil}$项取模），考虑平方相当于两个相同的多项式相乘，即$\sum_{i=0}^{n}G_iG_{n-i}$，这个式子任何时候都有一项的次数小于$x^{\left\lceil\frac{n}{2}\right\rceil}$，所以模数可以平方（注意只有右边为$0$才可以平方模数）
同时乘上$f(x)$，$g^2(x)f(x)+g’^2(x)f(x)-2g(x)g’(x)f(x)\equiv 0(\mod x^n)$
化简移项得$g(x)\equiv 2g’(x)-f(x)g’^2(x)(\mod x^n)$（注意这里是在模$x^n$的意义下所以$f(x)g’(x)$不能化简）
这样就可以通过$g’(x)$求出$g(x)$
发现$f(x)$在模$x^1$的意义下逆元为常数项的逆元，所以可以用常数项推出$f(x)$在模$x^n$意义的逆元，如果常数项没有逆元，$f(x)$也就没有逆元了
-
代码
-
多项式开根
多项式可以开根！
如果有$g^2(x)\equiv f(x)(\mod x^n)$，则$g(x)$是$f(x)$在模$x^n$意义下的平方根
跟多项式求逆的思路差不多，假设现在知道了$g’^2(x)\equiv f(x)(\mod x^{\left\lceil\frac{n}{2}\right\rceil})$
移项得
$g’^2(x)-f(x)\equiv 0(\mod x^{\left\lceil\frac{n}{2}\right\rceil})$
是不是又可以平方了？$(g’^2(x)-f(x))^2\equiv 0(\mod x^n)$
拆开得
$g’^4(x)+f^2(x)-2f(x)g’^2(x)\equiv 0(\mod x^n)$
移项化简得
$(\frac{g’^2(x)+f(x)}{2g’(x)})^2\equiv f(x)(\mod x^n)$
左边的那一坨就是要求的$g(x)$了
-
代码
-
多项式除法
多项式可以除法！
如果有$f(x)=g(x)G(x)+F(x)$，则$G(x)$为商，$F(x)$为余数
设$a’(x)$表示$x^na(\frac{1}{x})$，把$\frac{1}{x}$代入原式，两边再同乘$x^n$
$x^nf(\frac{1}{x})=x^ng(\frac{1}{x})G(\frac{1}{x})+x^nF(\frac{1}{x})$
发现可以用$a’(x)$代替一些多项式
$f’(x)=g’(x)G’(x)+x^{n-k+1}F’(x)$（$k$是$g(x)$的最高次）
$x^{n-k+1}F’(x)$的最低次项肯定要不小于$n-k+1$，而要求的$G(x)$的最高次项肯定要小于$n-k+1$的
所以在模$x^{n-k+1}$的情况下，$x^{n-k+1}F’(x)$可以被忽略而不影响$G(x)$
所以多项式求一下$g’(x)$的逆元，然后求出$G’(x)$从而得到$G(x)$
-
代码
-
多项式取模
多项式可以取模！
求出上面的$G(x)$然后求$F(x)=f(x)-g(x)G(x)$即可
-
代码
-
分治$FFT$（多项式分治）
多项式可以分治求解！
如果有$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$，并且已经知道$g(x)$每一项的系数，现在要快速求解$f(x)$的每一项系数，其中$f(0)=1$
考虑如果已知$f(l)\sim f(mid)$的值，就可以求出它们对于$f(mid+1)\sim f(r)$的贡献，对$x$的贡献即为$\sum_{i=l}^{mid}f(i)g(x-i)$
这样就类似一个$CDQ$分治的过程，可以$O(n\log^2n)$求解了
生成函数
-
普通型生成函数
对于一个数列，它的普通型生成函数就是$\sum_{i=0}^{∞}a_ix^i$
考虑这么一个问题：
$A$物品只能拿奇数个，$B$物品只能拿偶数个，求拿$n$个物品的方案数
$A$的生成函数为$x+x^3+x^5+…$，根据无穷项等比数列求和公式可得这个玩意是$\frac{x}{1-x^2}$
$B$的生成函数为$1+x^2+x^4+…$，这个玩意是$\frac{1}{1-x^2}$
则答案就是它们相乘后$x^n$的系数
普通型生成函数用来解决组合问题（物品不要求顺序）
-
指数型生成函数
对于一个数列，它的指数型生成函数就是$\sum_{i=0}^{∞}\frac{a_i}{i!}x^i$
考虑这么一个问题：
$A$物品只能拿奇数个，$B$物品只能拿偶数个，拿的顺序不同算不同方案，求拿$n$个物品的方案数
$A$的生成函数为$x+\frac{1}{3!}x^3+\frac{1}{5!}x^5+…$，这个玩意是$\frac{e^x-e^{-x}}{2}$
$B$的生成函数为$1+\frac{1}{2!}x^2+\frac{1}{4!}x^4+…$，这个玩意是$\frac{e^x+e^{-x}}{2}$
则答案就是它们相乘之后$x^n$的系数乘上$n!$的值
指数型生成函数用来解决排列问题（物品要求顺序）
-
列一些常用的公式
$1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+…=e^x$
$1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+…=e^{-x}$
$1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6}…=\frac{e^x+e^{-x}}{2}$
$x+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7}…=\frac{e^x-e^{-x}}{2}$
$x-\frac{x^2}{2}+\frac{x^3}{3}+…=\ln(1+x)$
$x-\frac{x^3}{3}+\frac{x^5}{5}+…=\sin x$
$1-\frac{x^2}{2}+\frac{x^4}{4}+…=\cos x$
$1+x+x^2+x^3+…=\frac{1}{1-x}$
$1+ax+\frac{a(a-1)x^2}{2!}+\frac{a(a-1)(a-2)x^3}{3!}+…=(1+x)^a$
拉格朗日插值
-
公式
记住得了
有$F(x)$，表示一个$N$次多项式，现在已经知道了它在给定的$n$个点下的值
则有$F(x)=\sum_{i=0}^{n}F(x_i)\prod_{j=0,j\not= i}^{n}\frac{x-x_j}{x_i-x_j}$，这样就可以$O(n^2)$求解了
