顯然記不住又必須記但還是記不住于是只能抄下來的結(jié)論
1.多項式暴力操作
多項式求逆：給定\(F(x)\)，求\(G(x)\)使得\(G(x)F(x)=1\)
\[g_i=-\frac{1}{f_0}\sum_{j=0}^{i-1}g_j\times f_{i-j}
\]
其中\(g_0=\frac{1}{f_0}\)。
多項式\(\ln\)：給定\(F(x)\)，保證\(f_0=1\)，求\(G(x)=\ln F(x)\)
\[g_i=f_i-\sum_{j=0}^{i-1}j\times g_j\times f_{i-j}
\]
其中\(g_0=0\)。
多項式\(\exp\)：給定\(F(x)\)，保證\(f_0=0\)，求\(G(x)=\ e^{F(x)}\)
\[g_i=\frac{1}{i}\sum_{j=1}^i j\times f_j\times g_{i-j}
\]
其中\(g_0=1\)。
2.范德蒙德行列式
\[\left |\begin{array}{cccc}
1 &1 & ... &1 \\
x_1 &x_2 &...&x_n \\
\vdots & \vdots & &\vdots\\
x_1^{n-1} & x_2^{n-1} &...&x_n^{n-1} \\
\end{array}\right|
\]
第一行可以視為\(x_1,x_2...x_n\)的\(0\)次冪，這樣的行列式的值為
\[\prod_{1\leq i<j\leq n}(x_j-x_i)
\]
3.一些組合恒等式
\[\sum_{\sum_{i=1}^m x_i =n}\prod_{i=1}^m\binom{x_i}{k_i}=\binom{n+m-1}{m-1+\sum_{i=1}^mk_i}
\]
\[\sum_{i=0}^{\min(n,m)}\binom{n}{i}\binom{m}{i}=\sum_{i=0}^{\min(n,m)}\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}
\]
4.奇妙位運算
\[a+b=(a|b)+(a\& b)
\]
一個集合每個數(shù)異或上\(c\)，對集合或和和與和的影響分別是
\[\cup'=(\cup\&～c)|(c\&～\cap)
\]
\[\cap'=(\cap\&～c)|(c\&～\cup)
\]
5.圓上整點個數(shù)
設(shè)\(f_d(x)\)表示在\(d\)維空間中半徑為\(x\)的圓上的整點個數(shù)，則\(\frac{f_d(x)}{2d}\)為積性函數(shù)。
浙公網(wǎng)安備 33010602011771號