高精度加法
vector<int> add(vector<int> A, vector<int> B) { // A: 4 3 2 1 // B: 6 5 vector<int> C(max(A.size(), B.size…
Category: ACM笔记
高精度乘法
vector<int> mul(vector<int> A, vector<int> B) { // A: 4 3 2 1 // B: 6 5 vector<int> C(A.size() + B.size() …
树状数组
树状数组笔记 树状数组功能 快速求前缀和O(long) 修改某一个数O(logn) 原理 基于二进制，$x = 2^{i_k} + 2^{i_{k-1}} + .... + 2^{i_1}$ $i_k >= i_{k-1} >= ....i_1， …
lowbit-计算整数在二进制最低位的位置
int lowbit(int x) { return x & (-x); } //返回最低位1的的位置的2^k，例如lowbit(8) = 2^3 == 8, lowbit(16) = 2 ^ 4 == 16
C++ biset用法
C++的 bitset 在 bitset 头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。 下面是具体用法 构造函数 bitset常用构造函数有四种，如下 bitset<4> bitset1; //无参构造，…
求余规则
模运算与基本四则运算有些相似，但是除法例外。其规则如下： (a + b) % p = (a % p + b % p) % p （1） (a - b) % p = (a % p - b % p) % p （2） (a * b) % p = (a % p * b …
分数取模——费马小定理
费马小定理:对于素数 M 任意不是 M 的倍数的 b，都有：b ^ (M-1) = 1 (mod M)于是可以拆成：b*b^(M-2)=1(mod M)a / b = a * (b ^ (M - 2)) (mod M)
分数取模——费马小定理
费马小定理:对于素数 M 任意不是 M 的倍数的 b，都有：b ^ (M-1) = 1 (mod M)于是可以拆成：b*b^(M-2)=1(mod M)a / b = a * (b ^ (M - 2)) (mod M)
线性筛
线性筛，primes里面存着2，3，5等等的素数，st数组里面存着某个数是不是质数 const int N = 2e4; int primes[N], cnt; bool st[N]; void get_primes(int n) { for (int i =…
快速幂模板
int qmi(int n, int k, int p) { int res = 1 % p; while (k) { if (k & 1) res = 1ll * res * n % p; n = 1ll * n * n % p; k >>…