搜索

算法数学笔记-零、常用数表及杂项


发布时间: 2022-11-24 17:36:08    浏览次数:20 次

突然发现博客园可以存笔记,这样就可以避免出门没带电脑而又想看笔记的情况了,还方便大家交流学习~

零、常用数表及杂项

常用数表

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);
复数相乘

几何定义:模长相乘,幅角相加

代数定义:

\[(a + bi) * (c + di) \\ = ac + adi + bci + bdi^2 \\ = ac + adi + bci - bd \\ = (ac - bd) + (bc + ad)i \]

WQS二分

WQS 二分通常用来解决下面这类问题:

给定若干 n 个物品,要求从中恰好选 M 次,最大化 / 最小化 选的物品权值和。

几个关键点:

1.正向二分(从 -inf ~ +inf)

2.先想清楚随着mid增大,m会增加还是减小

3.如果是m增大,则在check()中,同等优解的情况下,尽量使m更大,二分中寻找第一个check(mid) >= M的位置.

如果是m减小,则在check()中,同等优解的情况下,尽量使m更小,二分中寻找第一个check(mid) <= M的位置.

4.答案既是ans + M * mid 或 ans - M * mid(不是实际选择次数m * mid);

*2022/10/5 移除‘范德蒙德卷积’,新增于《四、组合数学》及推论
*2022/10/6 新增 ‘WQS二分’

免责声明 算法数学笔记-零、常用数表及杂项,资源类别:文本, 浏览次数:20 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 05:36:08。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/lyhy/p/16743052.html