Ender's blog

OI数学专题笔记 - 4 容斥原理 现有 {A1,A2,⋯ ,An}\{A_1, A_2, \cdots, A_n\}{A1​,A2​,⋯,An​} 总共 nnn 个集合，一直任意多个子集交集的大小，则所有集合并集的大小为： \sum_{B\subset\{A_1, A_2, \cdots, A_n\}} (-1)^{|B| + 1} \cdot |\cap_{A_i\inB}A_i| 随机试验 不能预先确知结果 实验之前可以预测所有可能结果或范围 可以在相同条件下重复实验 样本空间：随机试验所有可能结果组成的集合 连续性样本空间（不要求掌握）、离散样本空间、无穷样本空间 随机事件 样本空间的任意一个子集称之为事件 事件发生：在一次试验中，事件的一个样本点发生 必然事件：样本空间全集 不可能事件：空集 事件本身是样本空间的子集，所以事件的运算本质上是集合的运算。 概率 定义：为样本空间的每一个事件定义一个实数，这个实数称为概率。事件 AAA 的概率称为 P(A)P(A)P(A) 。 P(A)≥0P(A) \geq 0P(A ...

BSGS代码 在OI数学笔记三中，我写过BSGS算法，这里是代码。 123456789101112131415161718int z[1005];void bsgs(int a, int b, int p) { int sp = int(sqrt(p)); z[0] = 1; for(int i = 1; i < sp; i++) z[i] = 1ll * z[i - 1] * a % p; for(int i = 0; i < sp; i++) if(z[i] % p == b) return i; sort(z, z + sp); int asp = fastPower(a, sp, p); for(int i = 2, l = sp, r = sp + sp - 1; l <= n; l += sp, r += sp, i++) { int div = fastPower(asp, i - 1, p); div = fastPower(div, ...

组合数学习笔记 定义: 排列：从 nnn 个元素中选取 rrr 个元素，当考虑顺序时，所有可能的方案一共有： Anr=n!(n−m)!A_n^r = \frac{n!}{(n - m)!} Anr​=(n−m)!n!​ 组合：从 nnn 个元素中选取 rrr 个元素，当不计顺序时，所有可能的方案一共有： Cnr=(nr)=n!m!(n−m)!=AnmAmmC_n^r = \left ( n \\ r \right ) = \frac{n!}{m!(n - m)!} = \frac{A_n^m}{A_m^m} Cnr​=(nr)=m!(n−m)!n!​=Amm​Anm​​ 组合数递推公式 如果将杨辉三角形写出来的话： 111121133114641⋯⋯⋯⋯⋯⋯\begin{array}{l} 1 \\ 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ \cdots & \cdots & \cdots & \cd ...

高精度加减乘模板 这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。 其中要注意的是高精度减法需要均为正数，且大数减小数。如何比较大小？模板里面重载了 <<< 运算符，可以直接比较大小。 修改结构体中的 WIDTH 与 BASE 可以达到修改压位的位数的目的。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192struct BigInt { static const int BASE = 10000; static const int WIDTH = 4; int s[10005], n; BigInt(long long num = 0) {*this = num;} ...

素数筛法及线性筛求积性函数值学习笔记 定义 快速求出 1 n1 ~ n1 n 中所有素数的方法。 埃氏筛 12345678bool not_prime[1005];memset(not_prime, 0, sizeof(not_prime));not_prime[1] = true;for(int i = 2; i <= n; i++) if(!not_prime[i]) for(int j = i + i; j <= n; j += i) not_prime[j] = true; 枚举每一个质数的倍数，并将其打上标记，时间复杂度为 OnloglognO{nloglogn}Onloglogn 。 欧拉筛 为了达到线性筛 O(n)O(n)O(n) 的复杂度，每个数都只能被筛掉一次。 将 xxx 质因数分解，写为 x=p1r1⋅p2r2⋯pkrkx = p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k}x=p1r1​​⋅p2r2​​⋯pkrk​​ ，假设 p1<p2<⋯<p ...

快速乘法 快速乘的名字是从快速幂抄过来的，事实上它比直接乘要慢。 思路和快速幂一样，对于 k×xk \times xk×x ，可将其视为 k2×x+k2×x\frac{k}{2} \times x + \frac{k}{2} \times x2k​×x+2k​×x ，若 kkk 为奇数，则再加个 xxx 。 1234567int fastTimes(int x, int k, int p) { if(k == 0) return 0; int z = fastTimes(x, k >> 1, p); z = (z + z) % p; if(k % 2 == 1) z = (z + x) % p; return z;}

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 叫做积性函数。 如果取消互质的条件则叫做完全积性函数。 例如： I(n) = 1, id(n) = n 这两个就是完全积性函数 欧拉函数 ϕ(n)\phi(n)ϕ(n) ，莫比乌斯函数 μ\muμ 就是积性函数。 莫比乌斯函数： 对于 μ(n)\mu(n)μ(n) ，先对 nnn 分解质因数为 n=p1k1⋅p2k2⋯prkrn = p_1^{k_1} \cdot p_2^{k_2} \cdots p_r^{k_r}n=p1k1​​⋅p2k2​​⋯prkr​​ 则 μ(n)={1,n=1(−1)r,k1=k2=⋯=kr0,kt>1\mu(n) = \left \{ \begin{array}{l} 1, n = 1 \\ (-1)^r, k_1 = k_2 = \cdots = k_r \\ 0, k_t > ...

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

Miller-Rabin 素性测试代码 之前的笔记中讲过这个算法，所以在这里把代码贴一下。 123456789101112131415161718192021222324int prime[8] = {2, 3, 5, 8, 11, 13, 17, 37};bool miller_rabin(int n, int a) { int d = n - 1, r = 0; while(d % 2 == 0) d = d >> 1, r++; int z = fastPower(a, d, n); if(z == 1) return true; for(int i = 0; i < r; i++) { if(z == n - 1) return true; z = 1ll * z * z % n; } return false;}bool check(int n) { if(n < 2) return f ...

OI数学专题笔记 - 2 素数的定义和判定 定义 如果 ppp 只有 1 和 ppp 两个印子，则 ppp 为负数。 Miller-Rabin 素性测试 如果 nnn 为素数，取 a<na < na<n ，设 n−1=d×2rn - 1 = d \times 2^rn−1=d×2r ，则要么 ad≡1(modn)a^d \equiv 1 \pmod nad≡1(modn) ，要么 ∃0≤i<r,s.t.ad×2i≡−1(modn)\exists 0 \leq i < r, s.t. a^{d \times 2^i} \equiv -1 \pmod n∃0≤i<r,s.t.ad×2i≡−1(modn) 。（费马小定理的推广形式） 意思是：如果有一个素数 nnn ，任取 1≤a<n1 \leq a < n1≤a<n ，将 n−1n - 1n−1 分解为 n−1=d×2rn - 1 = d \times 2^rn−1=d×2r ，其中 ddd 为奇数， 则有如下两条性质至少有一条满足： ad≡1(modn)a^d \equiv ...