Ender's blog

组合数学习笔记 定义: 排列：从 nnn 个元素中选取 rrr 个元素，当考虑顺序时，所有可能的方案一共有： Anr=n!(n−m)!A_n^r = \frac{n!}{(n - m)!} Anr​=(n−m)!n!​ 组合：从 nnn 个元素中选取 rrr 个元素，当不计顺序时，所有可能的方案 ...

高精度加减乘模板 这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。 其中要注意的是高精度减法需要均为正数，且大数减小数。如何比较大小？模板里面重载了 <<< 运算符，可以直接比较大小。 修改结构体中的 WIDTH 与 BASE 可以达到修 ...

素数筛法学习笔记 定义 快速求出 1 n1 ~ n1 n 中所有素数的方法。 埃氏筛 12345678bool not_prime[1005];memset(not_prime, 0, sizeof(not_prime));not_prime[1] = true;for(int i = 2 ...

快速乘法 快速乘的名字是从快速幂抄过来的，事实上它比直接乘要慢。 思路和快速幂一样，对于 k×xk \times xk×x ，可将其视为 k2×x+k2×x\frac{k}{2} \times x + \frac{k}{2} \times x2k​×x+2k​×x ，若 kkk 为奇数，则再加个 ...

OI数学专题笔记 - 3 积性函数 如果函数 fff 满足 gcd(a,b)=1gcd(a, b) = 1gcd(a,b)=1 时有 f(ab)=f(a)f(b)f(ab) = f(a)f(b)f(ab)=f(a)f(b) ，则 fff 叫做积性函数。 如果取消互质的条件则叫做完全积性函 ...

扩展欧几里得算法（ExGCD）代码 之前的数学笔记中讲过这个算法，所以这里把代码贴一下。 123456789101112int exgcd(int a, int b, int& x, int& y) { if(b == 0) { x = 1 ...

Miller-Rabin 素性测试代码 之前的笔记中讲过这个算法，所以在这里把代码贴一下。 123456789101112131415161718192021222324int prime[8] = {2, 3, 5, 8, 11, 13, 17, 37};bool mi ...

OI数学专题笔记 - 2 素数的定义和判定 定义 如果 ppp 只有 1 和 ppp 两个印子，则 ppp 为负数。 Miller-Rabin 素性测试 如果 nnn 为素数，取 a<na < na<n ，设 n−1=d×2rn - 1 = d \times 2^rn−1= ...

矩阵快速幂学习笔记 快速幂 对于计算 xyx^yxy 只需要计算 xy2×xy2x^{\frac{y}{2}} \times x^{\frac{y}{2}}x2y​×x2y​ ，如果 yyy 是奇数只需要再乘 xxx ，这样就可以把 O(n)O(n)O(n) 的时间复杂度降为 O(logn)O( ...

高斯消元 基本高斯消元法 对于行列式： ∣a11a12a13...a1na21a22a23...a2na31a32a33...a3n...............an1an2an3...ann∣\left | \begin{array}{cccc} a_{1 1} & a_{1 2} & ...