目录
突然发现博客园可以存笔记，这样就可以避免出门没带电脑而又想看笔记的情况了，还方便大家交流学习~
零、常用数表及杂项
常用数表
| n= | 拆分数 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 10 | 42 | |||||||||
| 20 | 627 | |||||||||
| 30 | 5604 | |||||||||
| 40 | 37338 | |||||||||
| 50 | 204226 | |||||||||
| 60 | 966467 | |||||||||
| 70 | 4087968 | |||||||||
| 80 | 15796476 | |||||||||
| 90 | 56634173 | |||||||||
| 100 | 190569292 |
| （1~n中）n= | 本质不同的质因子个数和 | 质因子个数和 | 含有大于sqrt（i）的质因子的数的个数 | 最小质因子个数和 | 因子个数 | 因子个数平方 |
|---|---|---|---|---|---|---|
| 1e3 | 2126 | 2877 | 912 | 1609 | 7100 | 75083 |
| 1e4 | 24300 | 31985 | 9597 | 16121 | 93768 | 1504136 |
| 1e5 | 266400 | 343614 | 98106 | 161247 | 1167066 | 26324772 |
| 1e6 | 2853708 | 3626619 | 990892 | 1612490 | 13971034 | 421094344 |
| 1e7 | 30130317 | 37861249 | 9955052 | 16125085 | 162728526 | ... |
| n | 2n~3n | 2.8n~3.7n | n | 1.61n | nlogn | nlogn logn |
牛顿迭代
\(x_{i + 1} = x_i - \frac{f(x_i)}{f'(x_i)}\)
牛顿广义二项式定理
\(\alpha \in R \\ (x + y) ^ {\alpha} = \sum_{k = 0} ^ {\infty} {\alpha \choose k} x^{\alpha - k} y^k \\ { \alpha \choose k} = \frac{\alpha(\alpha - 1)...(\alpha - k + 1)}{k!}\)
一些结论
\(x {{x +k} \choose n} = (k +1) {{x + k} \choose {n + 1}} + (n - k) {{x + k + 1}\choose {n+1}}\)
对任意正整数x，\(\sum_{i - 1} ^ n {{i}\choose{x}} = {{n + 1}\choose{x + 1}}\)
对于矩阵A，满足\(A_{i,j} = ij*gcd(i, j)\)，高斯消元后，有：
\[A'_{i,j} = \begin{cases} ij\varphi(i) & i\ \ |j \\ 0 & i \not |j \end{cases} \]对于矩阵B，满足\(B_{i,j} = gcd(i, j)\),在高斯消元后，有：
\[B'_{i,j} = gcd(i,j) = \begin{cases} \varphi(i) & i \ \ | j \\ 0 & i\not | j \end{cases} \]\(ij = - \frac{i^2} 2 - \frac{j^2}{2} + \frac{(i + j) ^ 2}{2}\)
但i,j不一定有二次剩余, 所以
\(-ij = C^2_i + C^2_j - C^2_{i + j}\)
\(\sum _{i = 1} ^ \infty i ^{-2} = \frac{\pi ^ 2}{6}\)
\(\varphi(ij) = \frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}\)
给一个多项式除去\((1 + x)\)就相当于乘上\((1 - x + x^2 - x^3 + ... )\)可以使用前缀和优化，也可以理解为可撤销背包
使用斯特林数展开为下降幂：
\(x^n = \sum_{i = 0}^n {x \choose i} i! S(n, i) = \sum_{i = 0}^n S(n, i)x^{\underline{i}}\)
\(C_n^k *k^{\underline{m}} = C_{n - m} ^ {k - m} * n^{\underline{m}}\)
\(x^n = \sum_{k=0}^n Eular(n, k) {{x +k} \choose n}\)
子集枚举 (复杂度\(O(3^n)\))
for(int s = t; s; s = (s - 1) & t);
范德蒙德卷
\(\sum_{i = 0} ^ k {{n} \choose{i}}{{m}\choose{k - i}} = {{n + m}\choose k}\)
可以理解为在大小为n和m的两个堆中选择k个物品
好像是）推论：
\(\sum_{i = 0} ^ n {n \choose i}{n\choose {i - 1}} = {{2n} \choose {n - 1}}\)
复数相乘
几何定义：模长相乘，幅角相加
代数定义：
\[(a + bi) * (c + di) \\ = ac + adi + bci + bdi^2 \\ = ac + adi + bci - bd \\ = (ac - bd) + (bc + ad)i \] 标签：frac,sum,varphi,算法,choose,alpha,数表,杂项 From： https://www.cnblogs.com/lyhy/p/16743052.html