多项式爆零小技巧
Published:
每天一个爆零小技巧
——快乐爆零一百年
1.多项式爆零小技巧1
\[\cos x = 1 - \frac {x^2}{2!} + \frac {x^4}{4!} - \frac {x^6}{6!} + ...\]2.多项式爆零小技巧2
\[\sin x = x - \frac {x^3}{3!} + \frac {x^5}{5!} - \frac {x^7}{7!} + ...\]3.多项式爆零小技巧3
\[\ln (1+x) =x - \frac {x^2}{2} + \frac {x^3}{3} - \frac {x^4}{4} + ...\]4.多项式爆零小技巧4
\[-\ln (1-x) =x + \frac {x^2}{2} + \frac {x^3}{3} + \frac {x^4}{4} + ...\]5.多项式爆零小技巧5
\[\displaystyle (e^x-1)^m=m! \sum_{ n \ge 0 } \begin{Bmatrix} n \\ m \\ \end{Bmatrix} \frac { x^n } { n! }\]6.多项式爆零小技巧6
\[\displaystyle ( \ln \frac { 1 } { 1-x } )^m = m! \sum_{n \ge 0 } \begin{bmatrix} n \\ m \\ \end{bmatrix} \frac {x^n} {n!}\]7.多项式爆零小技巧7
对于某些枚举变量k的m次幂的问题，我们可以考虑先转化为下降幂，再进行如下变换以达到消参数
\[\binom {n} {k} k^{ \underline m } = \binom {n-m} {k-m} n^{ \underline m }\]8.多项式爆零小技巧8
对于 $ \displaystyle \Pi_i \frac { 1 } { 1 - x^i } $ 之类生成函数的卷积，若逐个卷积，复杂度将无法接受，那么我们先将所有的生成函数
下面的值全部取对，即 $ \displaystyle \sum_i \ln(1-x^i)$ ，考虑多项式爆零小技巧4我们可知对于一个 $ \displaystyle ln(1-x^i)$
$\displaystyle ln(1-x^i) =-1 \sum_{j \ge 1} \frac{ (x^i)^j }{ j }$
然后，我们就可以开心的 $exp$ 。
9.多项式爆零小技巧9
在 $FWT$ 中 $OR$ 卷积的实质为高维前缀和，即子集和。
10.多项式爆零小技巧10
\[\displaystyle \begin{bmatrix} n \\ k \\ \end{bmatrix} =(n - 1) \begin{bmatrix} n-1 \\ k \\ \end{bmatrix} + \begin{bmatrix} n-1 \\ k-1 \\ \end{bmatrix}\]11.多项式爆零小技巧11
\[\displaystyle \begin{Bmatrix} n \\ k \\ \end{Bmatrix} =k\begin{Bmatrix} n-1 \\ k \\ \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \\ \end{Bmatrix}\]12.多项式爆零小技巧12
\[\displaystyle x ^ n = \sum^n_{k=0} \begin{Bmatrix} n \\ k \\ \end{Bmatrix} x ^{ \underline{k}}\] \[\displaystyle x ^ {\underline{n}} = \sum^n_{k=0} \begin{bmatrix} n \\ k \\ \end{bmatrix} (-1)^{n-k} x^k\]13.多项式爆零小技巧13
\[\displaystyle x ^ {\overline{n}} = \sum^n_{k=0} \begin{bmatrix} n \\ k \\ \end{bmatrix} x ^ k\] \[\displaystyle x^n = \sum^n_{k=0} \begin{Bmatrix} n \\ k \\ \end{Bmatrix} (-1)^{n-k} x^{\overline{k}}\]14.多项式爆零小技巧14
\[\displaystyle \begin{Bmatrix} n \\ k \\ \end{Bmatrix} =\frac{1}{k!}\sum_{i=0}^k (-1)^i \binom {k} {i}(k-i)^n\]15.多项式爆零小技巧15
质数 $p$ 的原根数量是 $\phi(\phi(p))$，同时，当一个数 $g$ 是 $p$ 的原根时，$ g^{\frac{p-1}{p_i} } \neq 1 (\mod p) $ ($p_i$ 为 $p-1$ 的质因数)
16.多项式爆零小技巧16
单位根反演：
\[\displaystyle [k|n]=\frac{1}{k}\sum_{i=0}^{k-1}w_{k}^{ni}\]17.多项式爆零小技巧17
泰勒展开式：
\[f(x)=\sum \frac{f^{i'}(x_0)}{i!}(x-x_0)^i\]18.多项式爆零小技巧18
伽马函数：
\[\Gamma(x)=\int_0^\infty p^{x-1}e^{-p} dp\] \[amma(\frac{1}{2})=\sqrt \pi\] \[Gamma(1+\frac{1}{2})=\frac{1}{2}\Gamma(\frac{1}{2})=\frac{\sqrt \pi}{2}\] \[Gamma(x+1)=x!\]黎曼函数：
\[\zeta(x)=\displaystyle \sum_{i=1}^\infty \frac {1}{i^x}\] \[\zeta(x)=\frac{1}{\Gamma(x)} \int_0^\infty \frac{p^{x-1}}{e^p-1} dp\]贝塔函数：
\[B(p,q)=\int_0^1 x^{p-1}(1-x)^{q-1} dx\] \[B(p,q)=\frac{\Gamma(p)\Gamma(q)}{\Gamma(p+q)}\]19.多项式爆零小技巧19
设下降幂多项式 $f(x)$ 的系数生成函数($OGF$)为 $F(x)$ ，其点值的指数生成函数($EGF$)为 $G(x)$，那么 $G(x)=F(x)* e^x$ ，$F(x)=G(x)*e^{-x}$ 。
20.多项式爆零小技巧20
二项式反演：
\[\displaystyle f(n)=\sum_{i=0}^n\binom{n}{i}(-1)^i g(i) <-> g(n)=\sum_{i=0}^n\binom{n}{i}(-1)^i f(i)\] \[\displaystyle f(n)=\sum_{i=0}^n\binom{n}{i} g(i) <-> g(n)=\sum_{i=0}^n\binom{n}{i}(-1)^{n-i} f(i)\] \[\displaystyle f(n)=\sum_{i=n}^m\binom{i}{n} g(i) <-> g(n)=\sum_{i=n}^m\binom{i}{n}(-1)^{i-n} f(i)\]21.多项式爆零小技巧21
关于欧拉数：
\[\displaystyle x^n=\sum_{k=0}^{n-1} \left< n \atop k \right> \binom{x+k}{n}\] \[\displaystyle \left< n \atop k \right> =\sum_{i=0}^k \binom{n+1}{i}(k+1-i)^n(-1)^i\] \[\displaystyle \left< n \atop m \right>=\sum_{k=0}^n k! \begin{Bmatrix} n \\ k \\ \end{Bmatrix} \binom{n-k}{m}(-1)^{n-k-m}\]22.多项式爆零小技巧22
$ k\ minmax $ 容斥：
\[\displaystyle kthmax(S)=\sum_{T \subseteq S}(-1)^{|T|-k} \binom{|T|-1}{k-1} min(T)\] \[\displaystyle kthmin(S)=\sum_{T \subseteq S}(-1)^{|T|-k} \binom{|T|-1}{k-1} max(T)\]23.多项式爆零小技巧23
拉格朗日反演：
\[\displaystyle f(g(x))=x (g(f(x))=x )\] \[[x^n]f(x)=\frac{1}{n}[x^{-1}]\frac{1}{g(x)^n}\] \[\displaystyle [x^n]f(x)=\frac{1}{n}[x^{n-1}](\frac{x}{g(x)})^n\]扩展拉格朗日反演：
\[\displaystyle F(G(x))=x ( G(F(x))=x)\] \[\displaystyle [x^n]H(F(x))=\frac{1}{n}[x^{-1}]H'(x)\frac{1}{G(x)^n}\] \[\displaystyle [x^n]H(F(x))=\frac{1}{n}[x^{n-1}]H'(x)(\frac{x}{G(x)})^n\]24.多项式爆零小技巧24
高斯系数(表示 $p$ 进制 $n$ 维超空间内选 $m$ 维子空间的数量)：
\[\displaystyle \begin{bmatrix} n \\ m \\ \end{bmatrix}_p=\frac{\prod_{i=n-m+1}^n (p^i-1)}{\prod_{i=0}^m (p^i-1)}\] \[\displaystyle \begin{bmatrix} n \\ m \\ \end{bmatrix}_p=[x^m]\prod_{i=1}^{m}\frac{1}{1-p^i x}=[x^n]\prod_{i=1}^m\frac{x}{1-p^ix}\]25.多项式爆零小技巧25
循环矩阵 $A$ 的值为 $f(\xi)$ 。$f(x)$ 的系数为 $A$ 的系数，$\xi$ 为单位根。
26.多项式爆零小技巧26
给出一条结论：对于一个形式幂级数 $T(x)$ ，记 $f(x)$ 为一个集合幂级数，记 $\hat g(x)$ 为集合幂级数 $g(x)$ 的莫比乌斯变换 ，那么 $\hat T(f(x))=T(\hat f(x))$ 。
27.多项式爆零小技巧27
若我们求一类多项式 ：
\[\displaystyle F(x)=\sum_k\sum_ia_i^k x^k\]我们可以更改枚举方式使原式等于：
\[\displaystyle F(x)=\sum_i \frac{1}{1-a_ix}\]该式可以使用分治来处理。
28.多项式爆零小技巧28
当我们在处理子集卷积的时候，我们可能会使用到求逆、$\ln$、$\exp$，一般的 $O(n\log n)$ 求逆过于繁琐，一般使用 $O(n^2)$ 。
1.设 $PQ=1$
\[p_i= \begin{cases} \displaystyle \frac{1}{q_i}&i=0 \\ \displaystyle -\frac{1}{q_0}\sum_{j=0}^{i-1} p_j q_{i-j} &i\neq 0 \end{cases}\]2.设 $P=\ln(Q+1)$
\[\displaystyle p_i=q_i-\frac{1}{i} \sum_{j=0}^{i-1}j*p_{j}q_{i-j}\]3.设 $P=\exp(Q)$
\[\displaystyle p_i=\frac{1}{i}\sum_{j=0}^{i-1}(i-j)p_jq_{i-j}\]