茶茶白的C++模板

此处包含C++代码规范,C++模板,C++ STL的使用。

欢迎使用或转载代码块,唯一要求添加一行注释: https://dna049.com

编译器比你想象中的聪明,所以写让编译器好优化并且易读的代码,很多位运算,除法都是可以被优化的!
优质的代码本身就是一种解释,添加完全不必要的注释只会让人恶心
以后尽量使用 Vector 而非数组,虽然数组长度现在不用一开始给定,但是用Vector结合C++17可以简化代码!
以前觉得 main 函数 return 0 只是标准写法,现在(2020/5/22)才知道能返回就能提前优雅的结束!
全局变量数组元素自动默认初始化为0,局部变量要加= {}才会初始化为0

C++ 代码规范

此规范参考:Codeforces上 Jiangly 的码风,Menci 代码规范,知乎 pansz 的回答

总纲

  • 不再使用 using namespace std
  • 不建议使用 #include <bits/stdc++.h>
  • Tab 用于缩进,空格用于对齐(可不对齐)
  • 左大括号不换行(左大括号前有且仅有一个空格)
  • 头文件必须全部写在开头,C的头文件必须以c开头而非.h 结尾
  • main函数必须在整个程序末尾
  • 常用函数尽量写成类和模板形式
  • 尽量使用STL减少代码量
  • 尽量不要用C-type代码

空行

  • 不能有两个连续空行
  • 独立的代码块之间要有空行
  • 头文件块、函数、成员函数、结构体、类,全局变量块之间必须用空行隔开

空格

空格的作用:识别族群的位置

  • 前后必须都有空格:冒号、双目运算符、三目运算符
  • 前加后不加:* &
  • 后加前不加:关键字,逗号
  • 前后都不加:. -> ::

函数和变量

  • 传参时按照实际需要传 引用、const引用、值
  • 尽量不使用全局变量
  • 局部变量在用时定义
  • 在合适的时间使用static变量

命名

  • 统一使用驼峰命名法
  • 常量,typedef定义的类型 全部大写
  • 类私有变量以_开头
  • 函数和变量统一使用小驼峰
  • 结构和类统一使用大驼峰
  • 以Core结尾的核心代码是在约束条件下的高效代码
  • 以S结尾的是简单且效率较低的代码

注释

  • 代码尽量自注释
  • 在函数最开始注释,解释输入输出变量

代码优先级

  • 普通代码:正确,可行,可读,通用
  • Core代码:正确,高效,通用,可读

STL的使用

  • vector<bool> 不是vector类型,谨慎使用
  • 尽量用vector取代用户输入的数组,而非开足够大的数组
  • 尽量使用 emplace_back 取代 push_back,有些取代不了,就不取代了
  • 多使用 pair, tuple, sort, stable_sort, iota, accumulate, for_each, lambda函数 使得代码更加优雅

代码规范的说明

空格的作用是区分,空格缩进理论上是不合理的,强烈抵制四个空格代替Tab

双目运算符两边加空格是为了 区分运算符 和 变量,虽然a+b(这种代码不必加空格,但是为了养成好习惯,还是加上较好),关键字后面加空格是为了避免像 函数调用

工程中不推荐使用 using namespace std ,而且不用的时候你就会知道一些陌生的函数原来是std中的,并且以后修改起来很麻烦

不建议使用万能头文件,但是本人用了是因为,打CF等比赛的时候你一个个的敲头文件或者写一大堆头文件,还不如就写这一个,并且以后修改成不用万能头文件也很容易

左空格不换行完全是个人喜好,换不换都可以,固定就好

其它总纲的代码规范完全是为了代码通用美感,大道至简

尽量避免全局变量是因为防止程序不可控,降低代码耦合性,局部变量用的时候定义是为了增加代码可读性,static变量也是为了避免全局变量

驼峰命名的好处在于 “顾名思义,望文生义”(贬义褒用)
遵守代码规范,养成编程好习惯~

C++ 模板 by dna049 茶茶白

通用代码块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;
using BI = __int128; // for g++(64 bit)

int main(){
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
auto start = chrono::high_resolution_clock::now();

auto end = std::chrono::high_resolution_clock::now();
std::cout << "Time used: " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " (ms)" << std::endl;
return 0;
}
/*
/*------ Welcome to my blog: http://dna049.com ------*/
_ooOoo_
o8888888o
88" . "88
(| -_- |)
O\ = /O
____/`---'\____
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||- \
| | \\\ - /// | |
| \_| ''\---/'' | |
\ .-\__ `-` ___/-. /
___`. .' /--.--\ `. . __
."" '< `.___\_<|>_/___.' >'"".
| | : `- \`.;`\ _ /`;.`/ - ` : | |
\ \ `-. \_ __\ /__ _/ .-` / /
======`-.____`-.___\_____/___.-`____.-'======
`=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
佛祖保佑 永无BUG
*/

/**
* ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐
* └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │N L│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter │ │ 4 │ 5 │ 6 │ │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤
* │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ │Alt │ Space │ Alt│ │ │Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/

int128 在Linux下使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
__int128 read(){
__int128 x = 0, f = 1;
char ch = getchar();
while (ch<'0' || ch>'9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}

void printS(__int128 x){
if (x > 9) printS(x / 10);
putchar(x % 10 + '0');
}
void print(__int128 x){
if (x < 0) {
putchar('-');
x = -x;
}
printS(x);
}

int main(){
__int128 a = read();
print(a * a);
printf("\n");
return 0;
}

负数下标技巧

1
2
3
const int N = 1e5 + 2;
int aa[N];
int *a = (aa + N / 2);

优雅的输出技巧

1
2
3
4
int n = 10;
for(int i = 0; i < n; ++i) {
std::cout << i << " \n"[i==n-1];
}

向下取整 $\lfloor \frac{a}{n} \rfloor$ 和 向上取整 $\lceil \frac{a}{n} \rceil$

1
2
3
4
5
6
LL floor(LL a, LL n) { // n > 0
return a < 0 ? (a - n + 1) / n : a / n;
}
LL ceil(LL a, LL n) { // n > 0
return a < 0 ? a / n : (a + n - 1) / n;
}

注意到 C/C++ 中 ,整数除法 / 是向 0 取整(int(x)也是向0取整),但是Python(Sagemath) 整数除法// 是向下取整。

Barrent reduction 快速模,弃用,因为并不会变快…wiki镜像解释

对于给定常数$M$求 a % M,并要求 $ 0 \leq a < M^2$,并且 $a < 2^k$。因此下面 $k$ 的取值还是需要注意的。

1
2
3
4
5
6
7
8
constexpr LL M  = 1e9 + 7; // too big, M should satisfy M * M < int
constexpr int k = std::__lg(M) + 2;
constexpr LL m = (1LL << k) / M;

auto mod = [&](int a) {
LL r = a - ((a * m) >> k) * M;
return r >= M ? r - M : r;
};

输出全排列

1
2
3
4
5
6
7
8
9
10
void permutation(int n){
int x[n];
std::iota(x, x + n, 1);
do {
std::for_each(x,x+n,[](int &i){
std::cout << i;
});
std::cout << std::endl;
} while (std::next_permutation(x, x + n));
}

输出全排列对应的Python原理版本

1
2
3
4
5
6
7
8
9
10
11
12
13
def permutaion(n):
ans = [list(range(1,n+1))]
r = list(range(1,n+1))
while list(range(n,0,-1)) != r:
i = n-1
while r[i-1]>r[i]: i-=1
r[i-1],r[i] = r[i],r[i-1]
b = r.copy()
ans.append(b)
return ans

for i in range(1,6):
print(permutaion(i))

C++ 模板之初等数论

Greatest Common divisor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 简洁写法,不推荐,推荐使用内建 __gcd
LL gcd(LL a, LL b){
return b ? gcd(b, a % b) : a;
}
// lambda 表达式写法,开头不能是auto因为递归
std::function<int(int, int)> gcd = [&](int a, int b)->int{
return b == 0 ? a : gcd(b, a % b);
};
// 快速版本 https://cp-algorithms.com/algebra/euclid-algorithm.html 也没啥用,仅仅记录
int gcd(int a, int b) {
if (!a || !b) return a | b;
unsigned shift = __builtin_ctz(a | b);
a >>= __builtin_ctz(a);
do {
b >>= __builtin_ctz(b);
if (a > b) std::swap(a, b);
b -= a;
} while (b);
return a << shift;
}
// 普通版拓展GCD
LL exGcd(LL a, LL b, LL& x, LL& y){ // ax + by = gcd(a,b)
if (b == 0){
x = 1; y = 0; return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
// C++17版拓展GCD,优雅了不少!
std::tuple<LL, LL, LL> exGcd(LL a, LL b) { // ax + by = gcd(a,b)
if (b == 0) return {a, 1, 0};
auto [d, y, x] = exgcd(b, a % b);
return {d, x, y - a / b * x};
}

Sum of least common multiple $ s_n = \sum_{i=1} ^n lcm(i,n) $

所以,我们可以在 $O(n \log n)$ 处理好 $s_n$ 的前 $n$ 项。

Double sum of least common multiple $ ds_n = \sum_{1 \leq i \leq j \leq n} ^ n lcm(i,j) $

本来这个也挺麻烦,但是可以借助 $s_n$ 计算:$ds_n = \sum_{j=1} ^n s_j$,所以复杂度就一致了。当然也可以直接化简成:

不借助$s_n$ 其实也能暴力搞出来的。

模乘法逆元

1
2
3
LL inv(LL a, LL p){ // 0 < a < p and gcd(a,p) = 1
return a == 1 ? 1 : (p - p / a) * inv(p % a, p) % p;
}

上述代码主要用于线性时间预处理所有$p$以内的逆元,对于较小的常数$a$, 可以直接试除 b p mod a == 1

快速模乘法

1
2
3
4
5
6
7
8
9
10
template<typename T,typename U>
T powMod(T x,U n,T p){
T r(1);
while (n) {
if (n&1) r = r * x % p;
n >>= 1; x = x * x % p;
}
return r;
}
// 可以用for循环写的更短一点,但没必要

快速模加法

1
2
3
4
5
6
7
8
9
10
11
12
LL mulMod(LL x, LL n, LL p) {
LL r(0);
x %= p;
auto inc = [&](LL x, LL y) {
if ((x += y) >= p) x-=p;
};
while (n) {
if (n&1) inc(r,x);
n >>= 1; inc(x,x);
}
return r;
}

快速模加法下的快速模乘法

1
2
3
4
5
6
7
8
LL powMod(LL x, LL n, LL p){
LL r(1);
while (n){
if (n&1) r = mulmod(r, x, p);
n >>= 1; x = mulmod(x, x, p);
}
return r;
}

阶乘、组合数、Lucas定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int M = 1e9 + 2;
const int N = 3e5 + 2;
LL fac[N], ifac[N];
void init() {
fac[0] = 1;
for (int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % M;
ifac[N - 1] = powMod(fac[N - 1], M - 2);
for (int i = N - 1; i; --i) ifac[i - 1] = ifac[i] * i % M;
}
LL binom(int n, int k) {
//if (n < k) return 0;
return fac[n] * ifac[k] % M * ifac[n - k] % M;
}
LL lucas(LL n, LL m, LL p) { // C(n,m)%p, 仅在p较少时发挥作用
LL r = 1;
while (n && m) {
LL np = n % p, mp = m % p;
if (np < mp) return 0;
r = binom(np, mp);
n /= p, m /= p;
}
return r;
}

乞丐版素数判断

1
2
3
4
5
6
7
bool isPrime(int n) {
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2){
if (n % i == 0) return false;
}
return true;
}

$O(n \log n)$ 素数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
const int N =  1e7+2;
bool isP[N];

void initPrime(){
if(isP[2]) return;
isP[2] = true;
for (int i = 3; i < N; i += 2) isP[i] = true;
for (int i = 3; i < N; i += 2) if (isP[i]) {
for (int j = 3 * i; j < N; j += i * 2) {
isP[j] = false;
}
}
}

欧拉线性素数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N = 1e9 + 9;
bool isp[N];
std::vector<int> p;

void initPrimeP() {
if(isp[2]) return;
p.emplace_back(2);
isp[2] = true;
for (int i = 3; i < N; i += 2) isp[i] = true;
for (int i = 3; i < N; i += 2) {
if (isp[i]) p.emplace_back(i);
for (int j = 2, t = (N - 1) / i + 1; j != p.size() && p[j] < t; ++j) { // 用除号是防止溢出
isp[i * p[j]] = false;
// 不要下面的一步的话,复杂度 O(nloglogn), 但是不用除法,常数小
if (i % p[j] == 0) break;
}
}
}

大素数Miller-Rabin概率判别法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
bool witness(LL a, LL n, LL m, int t) {
LL x = powMod(a, m, n);
if (x == 1 || x == n - 1) return false;
while (t--) {
x = mulMod(x, x, n);
if (x == n - 1) return false;
}
return true;
}
bool rabin(LL n) {
if (n < 2) return false;
if (n == 2) return true;
if (!(n & 1)) return false;
LL m = n - 1;
int t = 0, cnt = 33;
while (!(m & 1)) {
++t;
m >>= 1;
}
while (cnt--) {
LL a = std::rand() % (n - 1) + 1;
if (Witness(a, n, m, t)) return false;
}
return true;
}

$O(1)$ (执行)时间复杂度判断一个数是否为素数!

奇技淫巧来源:https://codeforces.com/blog/entry/79941#comment-659202

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<int N>
struct Sieve {
bool isP[N];
constexpr Sieve(): isP() {
isP[2] = true;
for (int i = 3; i < N; i += 2) isP[i] = true;
for (int i = 3; i < N; i += 2) if (isP[i]) {
for (int j = 3 * i; j < N; j += i * 2) {
isP[j] = false;
}
}
}
};
// MAXN 默认最大值为1<<18=262144, 调节参数 -fconstexpr-loop-limit= 例如:
// g++ main.cpp -std=c++17 -fconstexpr-loop-limit=12345678 -fconstexpr-ops-limit=1234567890
// 使得 MAXN = 1e7+2
constexpr int MAXN = 1e5+2;
bool fast_is_prime(int n) {
static constexpr Sieve<MAXN> s;
return s.isP[n];
}

$O(n)$ 最小素因子预处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 2e8; // 再大内存吃不消了 
int sp[N], p[N];
int spf() {
int cnt = 1;
p[1] = 2;
for (int i = 2; i < N; i += 2) sp[i] = 2;
for (int i = 1; i < N; i += 2) sp[i] = i;
for (int i = 3; i < N; i += 2) {
if (sp[i] == i) p[++cnt] = i;
for (int j = 1; j <= cnt && p[j] <= sp[i] && i * p[j] < N; ++j) { //防止乘法溢出
sp[i * p[j]] = p[j]; // 注意到sp只被赋值一次
}
}
return cnt;
}

大整数的最小素因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LL pollardrho(LL n) {
LL x = std::rand() % (n - 1) + 1;
LL y = x, i = 1, k = 2, c = std::rand() % (n - 1) + 1;
while (true) {
x = (mulMod(x, x, n) + c) % n;
LL d = std::__gcd(y - x + n, n);
if (d > 1) return d;
if (++i == k) {
y = x;
if (k > n) return n;
k <<= 1;
}
}
}
LL ans;
void findp(LL n) {
if (rabin(n)) {
ans = std::min(ans, n);
return;
}
LL p = n;
while (p == n) p = pollardrho(n);
findp(p);
findp(n / p);
}

Mobius function

另类递推公式: $ \mu(i) = -\sum_{d|i,d<i} \mu(d) $。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 乞丐版
int getMu(int n){
if (n % 4 == 0) return 0;
int r = 1;
if (n % 2 == 0 ){
n /= 2;
r = -r;
}
for (int i = 3; i * i <= n; i += 2){
if (n % i == 0) {
n /= i;
if(n % i == 0) return 0;
r = -r;
}
}
return n > 1 ? -r : r;
}
// O(n log n) 预处理版本
const int N = 1e6 +2;
int mu[N];
void initmu() {
mu[1] = 1;
for (int i = 1; i < N; ++i) {
for (int j = i * 2; j < N; j += i) {
mu[j] -= mu[i];
}
}
}

// O(n) 预处理版
const int N = 1e6 + 2;
bool isp[N];
int p[N], mu[N];
int initmu() {
if(mu[1] == 1) return;
int cnt = 1;
p[1] = 2;
mu[1] = 1;
isp[2] = true;
for (int i = 3; i < N; i += 2) isp[i] = true;
for (int i = 3; i < N; i += 2) {
if (isp[i]) mu[i] = -1, p[++cnt] = i;
for (int j = 1, t = (N - 1) / i + 1; j <= cnt && p[j] < t; ++j) {
isp[i * p[j]] = false;
if (i % p[j] == 0) break;
mu[i * p[j]] = -mu[i];
}
}
for (int i = 2; i < N; i += 4) mu[i] = -mu[i >> 1];
return cnt;
}

Mobius function 前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int sumMu[N];
void initSumMu() {
if (mu[1] != 1) initmu();
for (int i = 1; i < N; ++i) sumMu[i] = sumMu[i - 1] + mu[i];
}
std::map<int, int> mp;
int getSumMu(int n) { // M(n) = M(n-1) + mu(n)
if (n < N) return sumMu[n];
auto it = mp.find(n);
if (it != mp.end()) return it->second;
int r = 1;
for (int i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
r -= (j - i + 1) * sumMu(n / i);
}
mp.insert(std::make_pair(n, r));
return r;
}
// Mobius function 绝对值前缀和
LL getSumAbsMu(LL n) { // Q(n) = Q(n-1) + |mu(n)|
LL r = 0;
for (LL i = 1, t; (t = i * i) < n; ++i) {
r += mu[i] * (n / t);
}
return r;
}

Euler ‘s totient function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
const int N = 1e7+2;
int phi[N];
void initPhi() {
if (phi[2] == 1) return;
for (int i = 1; i < N; i += 2) phi[i] = i;
for (int i = 2; i < N; i += 2) phi[i] = i >> 1;
for (int i = 3; i < N; i += 2) {
if (phi[i] != i) continue;
for (int j = i; j < N; j += i) phi[j] = phi[j] / i * (i - 1);
}
}
int getPhi(int n) {
int r = (n % 2 == 0 ? n/2 : n);
while (n % 2 == 0) n/=2;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
r = r / i *(i-1);
while (n % i == 0) n/=i;
}
}
if (n > 1) r = r / n * (n - 1);
return r;
}
LL sumPhi[N];
void initSumphi() {
if (phi[2] != 1) initPhi();
for (int i = 1; i < N; ++i) sumPhi[i] = sumPhi[i - 1] + phi[i];
}
std::map<int, LL> mp;
LL getSumphi(int n) {
if (n < N) return (LL) sumPhi[n];
auto it = mp.find(n);
if (it != mp.end()) return it->second;
LL r = LL(n + 1) * n / 2;
for (int i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
r -= (j - i + 1) * getSumphi(n / i);
}
mp.insert(std::make_pair(n, r));
return r;
}

$\pi(x)$ 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const int M = 7;
const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17;
int phi[PM + 1][M + 1], sz[M + 1];
void init() {
initprime();
pi[2] = 1;
for (int i = 3; i < N; ++i) {
pi[i] = pi[i - 1];
if (isp[i]) ++pi[i];
}
sz[0] = 1;
for (int i = 0; i <= PM; ++i) phi[i][0] = i;
for (int i = 1; i <= M; ++i) {
sz[i] = p[i] * sz[i - 1];
for (int j = 1; j <= PM; ++j) {
phi[j][i] = phi[j][i - 1] - phi[j / p[i]][i - 1];
}
}
}
LL primepi(LL x);
LL primephi(LL x, int s) {
if (s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s];
if (x / p[s] <= p[s]) return primepi(x) - s + 1;
if (x / p[s] / p[s] <= p[s] && x < N) {
int s2x = pi[(int)(sqrt(x + 0.2))];
LL ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2;
for (int i = s + 1; i <= s2x; ++i) {
ans += pi[x / p[i]];
}
return ans;
}
return primephi(x, s - 1) - primephi(x / p[s], s - 1);
}
LL primepi(LL x) {
if (x < N) return pi[x];
int ps2x = primepi(int(sqrt(x + 0.2)));
int ps3x = primepi(int(cbrt(x + 0.2)));
LL ans = primephi(x, ps3x) + LL(ps2x + ps3x - 2) * (ps2x - ps3x + 1) / 2;
for (int i = ps3x + 1, ed = ps2x; i <= ed; ++i) {
ans -= primepi(x / p[i]);
}
return ans;
}

$\pi(x)$ 函数计算的另一种做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int N = 1e7 + 2;
LL L[N], R[N];

LL primepi(LL n) {
LL rn = (LL) sqrt(n + 0.2);
for (LL i = 1; i <= rn; ++i) R[i] = n / i - 1;
LL ln = n / (rn + 1) + 1;
for (LL i = 1; i <= ln; ++i) L[i] = i - 1;
for (LL p = 2; p <= rn; ++p) {
if (L[p] == L[p - 1]) continue;
for (LL i = 1, tn = std::min(n / (p * p), rn); i <= tn; ++i) {
R[i] -= (i * p <= rn ? R[i * p] : L[n / (i * p)]) - L[p - 1];
}
for (LL i = ln; i >= p * p; --i) {
L[i] -= L[i / p] - L[p - 1];
}
}
return R[1];
}

求奇素数的一个原根

代码懒得贴,实际上暴力就可以了
首先,模 $m$ 有原根的充要条件是:$m=2,4,p^a,2p^a$,其中$p$为奇素数。
对于求模$p$的原根方法:对 $p-1$ 素因子分解:$p-1 = p_1^{a_1} \cdots p_s^{a_s}$ 若恒有

则 $g$ 是 模$p$的原根。对于 $p^a$ 可以用 $p$ 的原根简单构造,而 $2p^a$ 的原根为 $p^a$ 的原根 与 $p^a$ 的原根和 $p^a$的和中奇数者。(证明见P150《数论基础》潘承洞)
求所有原根见

数论函数的Dirichlet乘积

以前的代码不想贴了,不优雅,下次有题做的时候补上。

中国剩余定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pair<LL,LL> crt2(LL a1,LL m1,LL a2,LL m2){ // x = ai mod mi, m_i >0
LL t1,t2,ans = a2-a1;
LL d = exgcd(m1,m2,t1,t2);
assert(ans%d == 0);
LL m = m1/d*m2;
ans = (a1+ans/d*t1%m2*m1)%m; // %m2 是避免溢出
return make_pair(ans>0?ans:ans+m,m);
}
const int N = 22;
LL a[N],m[N];
pair<LL,LL> crt(int n){ // x = a[i] mod m[i], m[i] >0
pair<LL,LL> ans = make_pair(a[0]%m[0],m[0]);
for(int i=1;i<n;++i){
ans = crt2(ans.first,ans.second,a[i],m[i]);
}
return ans;
}

离散对数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LL baby_step_giant_step(LL a, LL b, LL p) { // a^x = b mod p
a %= p, b %= p;
if (a == 0) return b % p ? -1 : 1;
if (b == 1) return 0;
LL cnt = 0, t = 1;
for (LL g = std::__gcd(a, p); g != 1; g = std::__gcd(a, p)) {
if (b % g) return -1;
p /= g, b /= g, t = t * (a / g) % p;
++cnt;
if (b == t) return cnt;
}
std::map<LL, LL> mp;
LL m = LL(std::sqrt(p + 0.1) + 1);
LL base = b;
for (LL i = 0; i != m; ++i) {
mp[base] = i;
base = base * a % p;
}
base = powMod(a, m, p);
for (LL i = 1; i <= m + 1; ++i) {
t = t * base % p;
if (mp.count(t)) return i * m - mp[t] + cnt;
}
return -1;
}

模素数开根号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
LL modsqrt(LL a, LL p) { // find x s.t x*x=a mod p;
a = (p + a % p) % p;
if (a == 0) return 0;
if (p == 2) return (a & 1) ? 1 : 0;
LL q = (p - 1) >> 1;
if (powMod(a, q, p) != 1) return -1;
if (q & 1) return powMod(a, (q + 1) >> 1, p);
LL b, cnt = 1;
while (powMod(b = rand() % p, q, p) == 1); //find a non quadratic residue
while (!(q & 1)) ++cnt, q >>= 1;
b = powMod(b, q, p);
LL x = powMod(a, (q + 1) >> 1, p);
for (LL s = 1, t = powMod(a, q, p); t != 1; s = 1) { //keep x*x=t*a;t^{2^{cnt-1}}=1
for (LL tt = t * t % p; s < cnt && tt != 1; ++s) tt = tt * tt % p;
LL d = powMod(b, 1 << (cnt - s - 1), p);
x = (x * d) % p;
b = d * d % p;
t = t * b % p;
cnt = s;
}
return x;
}
LL mod_sqrt(LL a, LL p, int k = 1) { //find smallest x>=0 s.t x*x=a mod p^k
if (a == 0) return 0;
int ka = 0;
while (a % p == 0) a /= p, ++ka, --k;
if (k <= 0) return 0;
if (ka & 1) return -1;
auto pow = [](LL x, int n) {
LL r=1;
for (; n; n >>= 1, x *= x) if (n&1) r *= x;
return r;
};
LL n = pow(p, k), x;
if (p == 2) {
if (k == 1 || k == 2) x = a == 1 ? 1 : -1;
else if (a % 8 != 1) x = -1;
else {
x = 1;
for (int i = 4; i <= k; ++i) {
if ((x * x) % (1 << i) == a % (1 << i)) continue;
x += 1 << (i - 2);
}
}
} else x = mod_sqrt_p(a, n, p, k);
return x == -1 ? -1 : pow(p, ka >> 1) * (x < n - x ? x : n - x);
}

对于模一般的 $n$,先素因子分解分别求出答案,然后用中国剩余定理求最终解。

自然数方幂和 $O(k)$ 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const int N = 1e6 + 6;
int sp[N], p[N];
LL inv[N], AP[N], AS[N], f[N];
LL getPowSum(LL n, int k, LL mod) { // mod > k
if (k == 0) return n % mod;
if (p[0] != 2) spf();
int nk = k + 1;
LL tmp = 1;
for (int i = 2; i <= nk; ++i) tmp = tmp * i % mod;
inv[nk] = powMod(tmp, mod - 2, mod);
for (int i = nk - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= nk; ++i) {
if (sp[i] == i) f[i] = powMod(i, k, mod);
else f[i] = f[sp[i]] * f[i / sp[i]] % mod;
}
for (int i = 1; i <= nk; ++i) {
f[i] += f[i - 1];
if (f[i] >= mod) f[i] -= mod;
}
if (n <= nk) return f[n];
AP[0] = AS[nk] = 1;
for (int i = 1; i <= nk; ++i) AP[i] = AP[i - 1] * (n + 1 - i) % mod;
for (int i = nk - 1; i >= 0; --i) AS[i] = AS[i + 1] * (n - i - 1) % mod;
LL res = 0;
for (int i = 1; i <= nk; ++i) { // because f(i)=0
LL x = f[i] * AP[i] % mod * AS[i] % mod * inv[i] % mod * inv[nk - i] % mod;
if ((nk - i) & 1) res -= x; // be careful
else res += x;
}
return (res % mod + mod) % mod;
}

自然数方幂和精确版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <boost/multiprecision/cpp_int.hpp>
using BINT = boost::multiprecision::cpp_int;

BINT f[N];
BINT getpowsum(LL n, int k) { // k<1000
if (k == 0) return BINT(n);
if (p[0] != 2) spf();
int nk = 2 * k + 1;
f[0] = 0;
f[1] = 1;
auto bPow = [](BINT x, int n) -> BINT {
BINT r(1);
for (; n; x *= x, n >>= 1) if (n&1) r *= x;
return r;
};
for (int i = 2; i <= nk + 1; ++i) {
if (sp[i] == i) f[i] = bPow(BINT(i), k);
else f[i] = f[sp[i]] * f[i / sp[i]];
}
for (int i = 1; i <= nk; ++i) f[i] += f[i - 1];
if (n <= nk) return f[n];
BINT res = 0, tl = 1, tr = 1;
for (int i = nk - 1; i >= 0; --i) tr = tr * (n - i - 1) / (nk - i);
for (int i = 0; i <= nk; ++i) {
if ((nk - i) & 1) res -= f[i] * tl * tr;
else res += f[i] * tl * tr;
tl = tl * (n - i) / (i + 1);
tr = tr * (nk - i) / (n - i - 1);
}
return res;
}

需要下载boost包 类似的包还有NTL,GMP

NFT 正式可用版(last updated: 2020/7/9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const LL M = 998244353, ROOT = 3;
LL powMod(LL x, LL n) {
LL r(1);
while (n) {
if (n & 1) r = r * x % M;
n >>= 1;
x = x * x % M;
}
return r;
}
void bitreverse(std::vector<LL> &a) {
for (int i = 0, j = 0; i != a.size(); ++i) {
if (i > j) std::swap(a[i], a[j]);
for (int l = a.size() >> 1;
(j ^= l) < l; l >>= 1);
}
}
void nft(std::vector<LL> &a, bool isInverse = false) {
LL g = powMod(ROOT, (M - 1) / a.size());
if (isInverse) {
g = powMod(g, M - 2);
LL invLen = powMod(LL(a.size()), M - 2);
for (auto & x: a) x = x * invLen % M;
}
bitreverse(a);
std::vector<LL> w(a.size(), 1);
for (int i = 1; i != w.size(); ++i) w[i] = w[i - 1] * g % M;
auto addMod = [](LL x, LL y) {
return (x += y) >= M ? x -= M : x;
};
for (int step = 2, half = 1; half != a.size(); step <<= 1, half <<= 1) {
for (int i = 0, wstep = a.size() / step; i != a.size(); i += step) {
for (int j = i; j != i + half; ++j) {
LL t = (a[j + half] * w[wstep * (j - i)]) % M;
a[j + half] = addMod(a[j], M - t);
a[j] = addMod(a[j], t);
}
}
}
}
std::vector<LL> mul(std::vector<LL> a, std::vector<LL> b) {
int sz = 1, tot = a.size() + b.size() - 1;
while (sz < tot) sz *= 2;
a.resize(sz);
b.resize(sz);
nft(a);
nft(b);
for (int i = 0; i != sz; ++i) a[i] = a[i] * b[i] % M;
nft(a, 1);
a.resize(tot);
return a;
}

siyuan 的 FWT模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <cstdio>
#include <algorithm>
#include <vector>

const int P = 998244353;

void add(int &x, int y) {
(x += y) >= P && (x -= P);
}
void sub(int &x, int y) {
(x -= y) < 0 && (x += P);
}
struct FWT {
int extend(int n) {
int N = 1;
for (; N < n; N <<= 1);
return N;
}
void FWTor(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j + m], a[i + j]);
else sub(a[i + j + m], a[i + j]);
}
}
}
void FWTand(std::vector<int> &a, bool rev) {
int n = a.size();
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
if (!rev) add(a[i + j], a[i + j + m]);
else sub(a[i + j], a[i + j + m]);
}
}
}
void FWTxor(std::vector<int> &a, bool rev) {
int n = a.size(), inv2 = (P + 1) >> 1;
for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
int x = a[i + j], y = a[i + j + m];
if (!rev) {
a[i + j] = (x + y) % P;
a[i + j + m] = (x - y + P) % P;
} else {
a[i + j] = 1LL * (x + y) * inv2 % P;
a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
}
}
}
}
std::vector<int> Or(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTor(a1, false);
a2.resize(N), FWTor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTor(A, true);
return A;
}
std::vector<int> And(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTand(a1, false);
a2.resize(N), FWTand(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTand(A, true);
return A;
}
std::vector<int> Xor(std::vector<int> a1, std::vector<int> a2) {
int n = std::max(a1.size(), a2.size()), N = extend(n);
a1.resize(N), FWTxor(a1, false);
a2.resize(N), FWTxor(a2, false);
std::vector<int> A(N);
for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
FWTxor(A, true);
return A;
}
} fwt;

int main() {
int n;
scanf("%d", &n);
std::vector<int> a1(n), a2(n);
for (int i = 0; i < n; i++) scanf("%d", &a1[i]);
for (int i = 0; i < n; i++) scanf("%d", &a2[i]);
std::vector<int> A;
A = fwt.Or(a1, a2);
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], " \n"[i == n - 1]);
}
A = fwt.And(a1, a2);
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], " \n"[i == n - 1]);
}
A = fwt.Xor(a1, a2);
for (int i = 0; i < n; i++) {
printf("%d%c", A[i], " \n"[i == n - 1]);
}
return 0;
}

矩阵类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
LL mod;
class Matrix {
public:
const static int N = 102;
LL a[N][N];
int n;
Matrix() {}
Matrix(int _n, int x = 0): n(_n) { // xIn
all(0);
for (int i = 0; i < n; ++i) {
a[i][i] = x;
}
}
void all(int x) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = x;
}
}
}
Matrix operator + (const Matrix & A) const {
Matrix R(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
R.a[i][j] = a[i][j] + A.a[i][j];
if (R.a[i][j] >= mod) R.a[i][j] -= mod;
}
}
return R;
}
Matrix operator * (const Matrix & A) const {
Matrix R(n);
for (int i = 0; i < n; ++i) {
for (int k = 0; k < n; ++k) {
for (int j = 0; j < n; ++j) {
R.a[i][j] = (R.a[i][j] + a[i][k] * A.a[k][j]) % mod;
}
}
}
return R;
}
void print() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
std::cout << a[i][j] << " ";
}
std::cout << std::endl;
}
}
};
Matrix pow(Matrix A, int n) {
Matrix R(A.n, 1);
while (n) {
if (n&1) R = R * A;
n >>= 1; A = A * A;
}
return R;
}

注意到,矩阵乘法一定要写成上面的循环形式,这样利用高速缓存执行时间是原有的1/4

另外有序数组的累和要比无序的快很多,也是因为高速缓存(这个不太懂原理)

求$m$阶线性递推关系式第$n$项:时间复杂度$O(m^2 \log n)$,本质是做多项式的带模乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using LL=long long;
const LL mod = 1e9 + 7;
const int M = 1003;
LL c[M], ans[2 * M];

class RecSeq {
public:
LL a[2 * M];
int m;
RecSeq(int _m, LL x = 0): m(_m) {
std::memset(a, 0, sizeof (a));
a[0] = x;
}
RecSeq operator * (const RecSeq & A) const {
RecSeq R(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
R.a[i + j] = (R.a[i + j] + a[i] * A.a[j]) % mod;
}
}
for (int i = 2 * m - 2; i >= m; --i) {
for (int j = 0; j < m; ++j) {
R.a[i - m + j] += (R.a[i] * c[j]) % mod;
}
R.a[i] = 0;
}
for (int i = 0; i < m; ++i) {
R.a[i] %= mod;
}
return R;
}
};
template < typename T >
T tPow(T & A, LL n) {
T R(A.m, 1);
while (n) {
if (n & 1) R = R * A;
n >>= 1;
A = A * A;
}
return R;
}
void initC(int m) {
std::memset(c, 0, sizeof (c));
c[0] = c[m - 1] = 1;
for (int i = 1; i < m; ++i) {
ans[i] = 1;
}
ans[m] = 2;
for (int i = m + 1; i < 2 * m; ++i) {
ans[i] = ans[i - 1] + ans[i - m];
}
}
LL getans(LL n, int m) {
initC(m);
RecSeq A(m);
A.a[1] = 1;
RecSeq R = tPow(A, n - m);
LL r = 0;
for (int i = 0; i < m; ++i) {
r += (R.a[i] * ans[i + m]) % mod;
}
return r % mod;
}

利用多项式带模除法:Division with remainder的$O(m \log m)$算法,可优化到 $O(m \log m \log n)$,

但是如果递推关系中仅有常数个不为0,比如通常是两个,也可以不用多项式带模除法来搞,只需NFT就可以优化到 $O(m \log m \log n + m^2)$ (暂时不知道如何去掉$m^2$)

C++ 模板之数据结构

并查集

1
2
3
4
5
6
7
8
9
10
int find(int x) {
int ans = x;
while (ans != p[ans]) ans = p[ans];
while (x != ans) {
int t = p[x];
p[x] = ans;
x = t;
}
return ans;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct TreeArray {
const static int N = 2e5 + 2;
LL s[N];
int Size;
TreeArray() {}
TreeArray(int _S): Size(_S) {
for (int i = 0; i <= Size; ++i) s[i] = 0;
}
int lowbit(int n) {
return n & (-n);
}
void add(int id, int p) {
while (id <= Size) {
s[id] += p;
id += lowbit(id);
}
}
LL sum(int id) {
LL r = 0;
while (id) {
r += s[id];
id -= lowbit(id);
}
return r;
}
};

若设原始数组为 $a$, 设数字 $i$ 的二进制表示为 $d_1\ cdots d_n0\ dots 0, d_n = 1 $ 本质上树状数组 $s[i] $ 保存的其实是前 $n - 1 $ 位和 $i$ 一致, 且不超过 $i$ 的位置元素之和。

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#define lrt rt << 1
#define rrt rt << 1 | 1
#define lson l, m, lrt
#define rson m + 1, r, rrt
const int N = 1e5 + 5;
LL sum[N * 3], col[N * 3];
void pushUp(int rt) {
sum[rt] = sum[lrt] + sum[rrt];
}
void pushDown(int rt, int m) {
if (col[rt]) {
col[lrt] += col[rt];
col[rrt] += col[rt];
sum[lrt] += (m - (m >> 1)) * col[rt];
sum[rrt] += (m >> 1) * col[rt];
col[rt] = 0;
}
}
void build(int l, int r, int rt) {
if (l == r) {
scanf("%I64d", & sum[rt]);
return;
}
col[rt] = 0;
int m = (l + r) >> 1;
build(lson);
build(rson);
pushUp(rt);
}
void update(int L, int R, int p, int l, int r, int rt) {
if (L <= l && R >= r) {
sum[rt] += p * (r - l + 1);
col[rt] += p;
return;
}
pushDown(rt, r - l + 1);
int m = (l + r) >> 1;
if (L <= m) update(L, R, p, lson);
if (R > m) update(L, R, p, rson);
pushUp(rt);
}
LL query(int L, int R, int l, int r, int rt) {
if (L <= l && R >= r) return sum[rt];
pushDown(rt, r - l + 1);
int m = (l + r) >> 1;
LL ans = 0;
if (L <= m) ans += query(L, R, lson);
if (R > m) ans += query(L, R, rson);
return ans;
}

吊打线段树的珂朵莉树( Chtholly Tree)

RMQ 求区间最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class RMQ {
static
const int N = 100005;
public:
int n;
int a[N][20]; //a[i][j]=max(s[i]---s[i+2^j-1])
RMQ(int * s, int _n): n(_n) {
for (int i = 0; i != n; ++i) a[i][0] = s[i];
int len = (int)(log(double(n)) / log(2.0)) + 2;
for (int i = 1; i != len; ++i) {
for (int j = 0; j <= n - (1 << i); ++j) {
a[j][i] = max(a[j][i - 1], a[j + (1 << (i - 1))][i - 1]);
}
}
}
int Max(int l, int r) { // 0 <= l <= r < n
int len = (int)(log(double(r - l + 1)) / log(2.0));
return max(a[l][len], a[r - (1 << len) + 1][len]);
}
};

最长( 严格) 递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
int LIS(int a[], int n) { // longest increasing subsquence
if (n <= 0) return 0;
int * b = new int[n];
b[0] = a[0];
int k = 0;
for (int i = 1; i != n; ++i) {
if (a[i] > b[k]) b[++k] = a[i];
else b[lower_bound(b, b + k, a[i]) - b] = a[i];
}
return k + 1;
}
// lower_bound(first,end,val) 表示在单增 [frist,end) 中首次大于等于 val 的位置
// upper_bound(first,end,val) 表示在单增 [frist,end) 中首次大于 val 的位置

我们经常用二分答案的思想, 但是其实二分答案是仅仅知道其单调的情况下的策略, 实际上, 对于具体的问题, 我们完全可以对 $m$ 的值进行不同的处理, 而非单纯的 $m = (l + r) >> 1 $。

背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int MAX = 1e5 + 5;
int r[MAX];
void pack(int cash, int num, int v, int w) {
if (num == 0 || w == 0 || v == 0) return;
if (num == 1) { // 0-1背包
for (int i = cash; i >= v; --i)
r[i] = max(r[i], r[i - v] + w);
return;
}
if (num * v >= cash - v + 1) { //完全背包
for (int i = v; i <= cash; ++i)
r[i] = max(r[i], r[i - v] + w);
return;
}
int q[MAX], s[MAX], head, tail;
for (int j = 0; j < v; ++j) { //多重背包
q[0] = r[j];
s[0] = head = tail = 0;
for (int i = 1, k = j + v; k <= cash; ++i, k += v) {
q[i] = r[k] - i * w;
while (s[head] < i - num) ++head;
while (head <= tail && q[tail] < q[i]) --tail;
s[++tail] = i;
q[tail] = q[i];
r[k] = q[head] + i * w;
}
}
}

堆与STL优先队列

可以使用C++STL 的 priority_queue,查找可用 lower_bound 和 upper_bound。C++ STL 中优先队列是用堆来实现的。用途十分广泛,例如加速最小生成树,拓扑排序,等等。
堆的实现一般是用数组。 我们可以用 1 作为树的根, 对每一个节点 $x$, 它的两个节点分别就是 $2x$ 和 $2x + 1 $ 平时都用 $x << 1, x << 1 | 1 $ 表示。 堆只支持三个操作, 1. 插入一个节点(我们实现时是插入最尾部, 这样保证了是一个完全二叉树) $O(\log n) $ 2. 删除最大键值节点( 删除根元素的值) $O(\log n) $ 3. 输出最大键值节点( 查看根元素的值) $O(1) $

单调队列, 单调栈, 树状数组, 堆, 线段树, 红黑树 是我掌握的也很喜欢的几个数据结构了。

拓扑排序反字典序输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const int M = 200005;
const int N = 100005;
int head[N], sc, d[N], ans[N];
bool v[N];
struct Node {
int ed;
int next;
}
e[M];
void addedge(int x, int y) {
e[sc].ed = y;
e[sc].next = head[x];
head[x] = sc++;
++d[x];
}
void init(int n) {
sc = 1;
for (int i = 1; i <= n; ++i) {
head[i] = -1;
d[i] = 0;
v[i] = false;
}
}
void topoSort(int n) { // after read data
std::priority_queue<int > q;
for (int i = 1; i <= n; ++i) {
if (d[i] == 0) q.push(i);
}
while (!q.empty()) {
int u = q.top();
q.pop();
if (v[u]) continue;
v[u] = true;
for (int i = head[u]; i != -1; i = e[i].next) {
if (--d[e[i].ed] == 0) q.push(e[i].ed);
}
}
}

红黑树 red-black tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
class RBT {
typedef int elemType;
struct Node {
const static bool RED = 0;
const static bool BLACK = 1;
Node * ch[2], * fa; // x->fa->ch[x->rs] = x
int sz;
elemType key;
bool color, rs; // is rightson
};
Node * root; // root has no father
void faSon(Node * x, Node * y, bool rs) {
y->fa = x;
y->rs = rs;
x->ch[rs] = y;
}
void newNode(Node * x, elemType val, bool rs) { // x->ch[rs]=null
Node * p = new Node;
p->ch[0] = p->ch[1] = null;
p->sz = 1;
p->key = val;
p->color = Node::RED;
faSon(x, p, rs);
++x->sz;
}
void rotate(Node * x, bool rs) { // x must not null
Node * y = x->ch[!rs];
if (y == null) return;
if (x == root) root = y;
else faSon(x->fa, y, x->rs);
faSon(x, y->ch[rs], !rs);
faSon(y, x, rs);
y->sz = x->sz;
x->sz = x->ch[0]->sz + x->ch[1]->sz + 1;
}
void insMaintain(Node * x) { // x->color is RED
if (x == root || x->fa->color == Node::BLACK) return;
if (x->fa->fa->ch[!x->fa->rs]->color == Node::BLACK) {
if (x->rs ^ x->fa->rs) rotate(x->fa, x->fa->rs);
else x = x->fa;
x->color = Node::BLACK;
x->fa->color = Node::RED;
rotate(x->fa, !x->rs);
} else {
x = x->fa->fa;
x->color = Node::RED;
x->ch[0]->color = x->ch[1]->color = Node::BLACK;
insMaintain(x);
}
}
void delCase1(Node * x, Node * y) {
y->color = Node::BLACK;
y->fa->color = Node::RED;
y = y->ch[!y->rs];
rotate(x->fa, x->rs);
delCase2(x, y);
}
void delCase2(Node * x, Node * y) {
if (y->ch[y->rs]->color == Node::BLACK) {
if (y->ch[!y->rs]->color == Node::BLACK) {
y->color = Node::RED;
delMaintain(y->fa);
} else {
y->color = Node::RED;
y->ch[!y->rs]->color = Node::BLACK;
rotate(y, y->rs);
delCase3(y->fa);
}
} else delCase3(y);
}
void delCase3(Node * y) {
y->color = y->fa->color;
y->ch[y->rs]->color = y->fa->color = Node::BLACK;
rotate(y->fa, !y->rs);
}
void delMaintain(Node * x) {
if (x == root || x == null) return;
if (x->color == Node::RED) {
x->color = Node::BLACK;
return;
}
Node * y = x->fa->ch[!x->rs];
if (y->color == Node::RED) delCase1(x, y);
else delCase2(x, y);
}
Node * pred(Node * x, elemType val) { // max elem <= val
if (x == null) return null;
if (x->key > val) return pred(x->ch[0], val);
else if (x->ch[1] == null) return x;
return pred(x->ch[1], val);
}
Node * succ(Node * x, elemType val) { // min elem >= val
if (x == null) return null;
if (x->key < val) return succ(x->ch[1], val);
else if (x->ch[0] == null) return x;
return succ(x->ch[0], val);
}
int rank(Node * x, elemType val) { // count elem <= val
if (x == null) return 0;
if (x->key > val) return rank(x->ch[0], val);
return x->ch[0]->sz + 1 + rank(x->ch[1], val);
}
Node * select(Node * x, int k) { // k-th smallest elem
if (x == null || x->sz < k) return null;
int sz = x->ch[0]->sz + 1;
if (sz == k) return x;
if (sz < k) return select(x->ch[1], k - sz);
return select(x->ch[0], k);
}
void clear(Node * x) {
if (x->ch[0] != null) clear(x->ch[0]);
if (x->ch[1] != null) clear(x->ch[1]);
if (x != null) delete x;
}
void print(Node * x) {
printf("key = %d, sz = %d ", x->key, x->sz);
puts(x->color == Node::RED ? "RED" : "BLACK");
if (x->ch[0] != null) print(x->ch[0]);
if (x->ch[1] != null) print(x->ch[1]);
}
public:
const static int INF = 0x3f3f3f3f;
Node * null;
RBT() {
null = new Node; // no key, rs, father
null->ch[0] = null->ch[1] = null;
null->sz = 0;
null->color = Node::BLACK;
root = null;
null->key = INF; // for convenient
}
Node * search(elemType val) {
Node * x = root;
while (x != null) {
if (val == x->key) return x;
x = x->ch[val >= x->key];
}
return null;
}
void insert(elemType val) {
if (root == null) {
root = new Node; // no father, rs
root->ch[0] = root->ch[1] = null;
root->sz = 1;
root->color = Node::BLACK;
root->key = val;
return;
}
Node * x = root;
while (x->ch[val >= x->key] != null) {
++x->sz;
x = x->ch[val >= x->key];
}
newNode(x, val, val >= x->key);
insMaintain(x->ch[val >= x->key]);
root->color = Node::BLACK;
}
void del(elemType val) {
Node * x = search(val), * y;
if (x == null) return;
while (x->ch[0] != null || x->ch[1] != null) {
bool rs = 0;
if (x->ch[rs] == null) rs = !rs;
y = x->ch[rs];
while (y->ch[!rs] != null) y = y->ch[!rs];
std::swap(x->key, y->key);
x = y;
if (x->color == Node::RED) break;
}
delMaintain(x);
root->color = Node::BLACK;
y = x;
while (y != root) {
y = y->fa;
--y->sz;
}
if (x == root) root = null;
else if (x->ch[0] != null) faSon(x->fa, x->ch[0], x->rs);
else if (x->ch[1] != null) faSon(x->fa, x->ch[1], x->rs);
else x->fa->ch[x->rs] = null;
delete x;
}
elemType pred(elemType val) {
return pred(root, val)->key;
}
elemType succ(elemType val) {
return succ(root, val)->key;
}
int rank(elemType val) {
return rank(root, val);
}
elemType select(int k) {
return select(root, k)->key;
}
void clear() {
clear(root);
root = null;
}
int size() {
return root->sz;
}
void print() {
if (root != null) print(root);
}
int getans(int a, int k) { // for particular use
return select(root, rank(root, a) + k)->key;
}
};

C++ 模板之图论

图论还是一个特别强的工具。 为什么没有图论的STL?

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class LinkStar {
public:
std::vector<int> head, nxt, to;
LinkStar(int n) {
nxt.clear();
to.clear();
head = std::vector<int>(n + 1, -1);
}
void addedge(int u, int v) {
nxt.push_back(head[u]);
head[u] = to.size();
to.push_back(v);
}
};

知乎上看到YYYYLLL 关于Floyd 算法的解释挺好的,再次记录(稍加修改):

1
2
3
4
DP[k][i][j] 表示只经过 1~k 号节点优化,i 点到 j 点的最短路径长度。
则 DP[k][i][j] = min( DP[k-1][i][j], DP[k-1][i][k]+DP[k-1][k][j] )
= min( DP[k-1][i][j], DP[k][i][k]+DP[k][k][j] )
DP[0][][] 是初始图的邻接矩阵,DP[n][][] 就是最终求得的最短路长度矩阵了

本来一开始是没法做空间优化的, 但是第二个等式, 就保证了可以做空间优化

1
2
3
4
5
6
7
8
const int N = 102;
LL dp[N][N];
void Floyd(int n){
for(int k = 0; k!=n;++k)
for(int i<0; i!=n;++i)
for(int j=0;j!=n;++j)
dp[i][j] = std::min(dp[i][j],dp[i][k] + dp[k][j]);
}

dfs 序

1
2
3
4
5
6
7
8
int ncnt = 0; // init every case
void dfs(int x, int fa) { // dfs order
L[x] = ++ncnt;
for (int i = head[x]; i != -1; i = e[i].next) {
if (e[i].ed != fa) dfs(e[i].ed, x);
}
R[x] = ncnt;
}

笛卡尔树 :我去,竟然是$O(n)$复杂度的建树!

OI - wiki 中看到的讲解和复杂度分析!,注意到右链是从尾巴网上查找的。
hdu 1506

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct Node {
int id, val, par, ch[2];
void init(int _id, int _val, int _par) {
id = _id, val = _val, par = _par, ch[0] = ch[1] = 0;
}
};
int cartesian_build(Node * tree, int n) {
for (int i = 1; i <= n; ++i) {
int k = i - 1;
while (tree[k].val > tree[i].val) k = tree[k].par;
tree[i].ch[0] = tree[k].ch[1];
tree[k].ch[1] = i;
tree[i].par = k;
tree[tree[i].ch[0]].par = i;
}
return tree[0].ch[1];
}
int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
while (std::cin >> n) {
if (n == 0) break;
Node tree[n + 1];
tree[0].init(0, 0, 0);
for (int i = 1, x; i <= n; ++i) {
cin >> x;
tree[i].init(i, x, 0);
}
int root = cartesian_build(tree, n);
LL ans = 0;

function < int(int) > dfs = [ & ](int x) -> int {
if (x == 0) return 0;
int sz = dfs(tree[x].ch[0]);
sz += dfs(tree[x].ch[1]);
ans = max(ans, LL(sz + 1) * tree[x].val);
return sz + 1;
};
dfs(root);
std::cout << ans << std::endl;
}
return 0;
}

这就给出了一个$O(n) $复杂度求出包含 i且以 a[i] 为最小值的区间的方法。 太强了!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int root = cartesian_build(tree, n);
int l[n + 1], r[n + 1];

function<void(int)> getinterval = [ & ](int x) {
if (x == 0) return;
if (tree[tree[x].par].ch[0] == x) {
r[x] = tree[x].par - (tree[x].val != tree[tree[x].par].val);
l[x] = l[tree[x].par];
} else {
l[x] = tree[x].par + (tree[x].val != tree[tree[x].par].val);
r[x] = r[tree[x].par];
}
getinterval(tree[x].ch[0]);
getinterval(tree[x].ch[1]);
};
l[root] = 1;
r[root] = n;
getinterval(tree[root].ch[0]);
getinterval(tree[root].ch[1]);
for (int i = 1; i <= n; ++i) {
std::cout << l[i] << " " << r[i] << std::endl;
}

洛谷 T126268 「SWTR-05」Subsequence 有一个典型的应用

最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct Node {
int t, w, next;
}
a[N * N];
int n, ss, head[N], p[N], flow[N], c[N], h[N], numh[N];
void addedge(int x, int y, int w) {
a[ss].t = y;
a[ss].w = w;
a[ss].next = head[x];
head[x] = ss++;
}
int max_flow(int s, int t) {
int flow, ans = 0, neck, k;
std::memset(h, 0, sizeof (h));
std::memset(numh, 0, sizeof (numh));
std::memset(p, -1, sizeof (p));
for (int i = 1; i <= n; ++i) c[i] = head[i];
numh[0] = n;
int u = s;
while (h[s] < n) {
if (u == t) {
flow = 1e9;
for (int i = s; i != t; i = a[c[i]].t) {
if (flow > a[c[i]].w) {
neck = i;
flow = a[c[i]].w;
}
}
for (int i = s; i != t; i = a[c[i]].t) {
a[c[i]].w -= flow;
a[c[i] ^ 1].w += flow;
}
ans += flow;
u = neck;
}
for (k = c[u]; k != -1; k = a[k].next) {
if (a[k].w && h[u] == h[a[k].t] + 1) break;
}
if (k != -1) {
c[u] = k;
p[a[k].t] = u;
u = a[k].t;
} else {
if (0 == --numh[h[u]]) break;
c[u] = head[u];
k = n;
for (int i = head[u]; i != -1; i = a[i].next) {
if (a[i].w) k = std::min(k, h[a[i].t]);
}
h[u] = k + 1;
++numh[h[u]];
if (u != s) u = p[u];
}
}
return ans;
}

Stoer - Wagner 最小割

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N = 102;
int p[N], dis[N], mp[N][N];
bool vis[N];
int mincut(int n) {
int ret = 0x7fffffff;
for (int i = 0; i != n; ++i) p[i] = i;
while (n > 1) {
int t = 1, s = 0;
for (int i = 1; i != n; ++i) {
dis[p[i]] = mp[p[0]][p[i]];
if (dis[p[i]] > dis[p[t]]) t = i;
}
std::memset(vis, 0, sizeof (vis));
vis[p[0]] = true;
for (int i = 1; i < n; ++i) {
if (i == n - 1) {
if (ret > dis[p[t]]) ret = dis[p[t]];
for (int j = 0; j != n; ++j) {
mp[p[j]][p[s]] += mp[p[j]][p[t]];
mp[p[s]][p[j]] = mp[p[j]][p[s]];
}
p[t] = p[--n];
}
vis[p[t]] = true;
s = t;
t = -1;
for (int j = 1; j != n; ++j) {
if (!vis[p[j]]) {
dis[p[j]] += mp[p[j]][p[s]];
if (t == -1 || dis[p[j]] > dis[p[t]]) t = j;
}
}
}
}
return ret;
}

最短路SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

const int INF = 0x3f3f3f3f;
const int M = 2000005;
const int N = 1004;
int head[N], rehead[N], dist[N], sc, v[N];
struct A {
int id;
int g;
A() {}
A(int x, int y): id(x), g(y) {}
bool operator < (const A & a) const {
return g + dist[id] > a.g + dist[a.id];
}
};
struct Node {
int ed;
int w;
int next;
}
e[M];
void addedge(int x, int y, int z) {
e[sc].ed = y;
e[sc].w = z;
e[sc].next = head[x];
head[x] = sc++;
e[sc].ed = x;
e[sc].w = z;
e[sc].next = rehead[y];
rehead[y] = sc++;
}
void spfa(int s) {
std::memset(v, 0, sizeof (v));
std::memset(dist, 0x3f, sizeof (dist));
dist[s] = 0;
v[s] = true;
std::queue < int > q;
q.push(s);
while (!q.empty()) {
int u = q.front();
for (int i = rehead[u]; i != -1; i = e[i].next) {
int ed = e[i].ed;
if (dist[ed] > dist[u] + e[i].w) {
dist[ed] = dist[u] + e[i].w;
if (!v[ed]) {
v[ed] = true;
q.push(ed);
}
}
}
v[u] = false;
q.pop();
}
}

二维凸包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const int N = 501;
int vc[N];
struct Node {
int x, y, id;
bool operator != (const Node & A) const {
return x != A.x || y != A.y;
}
bool operator < (const Node & A) const {
if (y == A.y) return x < A.x;
return y < A.y;
}
}p[N], q[N];
bool crossLeft(const Node & op,
const Node & sp,
const Node & ep) {
return (sp.x - op.x) * (ep.y - op.y) > (sp.y - op.y) * (ep.x - op.x);
}
int graham(int n) {
sort(p, p + n);
if (n == 0) return 0;
q[0] = p[0];
if (n == 1) return 1;
q[1] = p[1];
if (n == 2) return 2;
q[2] = p[2];
int top = 1;
for (int i = 2; i != n; ++i) {
while (top && crossLeft(q[top], p[i], q[top - 1])) --top;
q[++top] = p[i];
}
int len = top;
q[++top] = p[n - 2];
for (int i = n - 3; i != -1; --i) {
while (top != len && crossLeft(q[top], p[i], q[top - 1])) --top;
q[++top] = p[i];
}
return top;
}

几类根号算法

$ s(n) = \sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor $

1
2
3
4
5
6
7
8
LL getsum(LL n) {
LL sum = 0;
for (LL i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
sum += (j - i + 1) * (n / i);
}
return sum;
}

$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor f(i)$

1
2
3
4
5
6
7
LL getsum(int n, int m) { // g[i]=f[i]+g[i-1]
LL sum = 0;
for (int i = 1, j; i <= min(n, m); i = j + 1) {
j = min(n / (n / i), m / (m / i) sum += LL(n / i) * (m / i) * (g[j] - g[i - 1]);
}
return sum;
}

$h(n) = \frac{n(n-1)(n-2)}{3} - \sum_{i=2}^n h(\lfloor \frac{n}{i} \rfloor)$

1
2
3
4
5
6
7
8
9
10
11
12
13
std::map<int, int> mp;
int getans(int n) {
auto it = mp.find(n);
if (it != mp.end()) return it->second;
int r = LL(n) * (n - 1) % M * (n - 2) % M * inv3 % M;
for (int i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
r -= LL(j - i + 1) * getans(n / i) % M;
if (r < 0) r += M;
}
mp.insert(std::make_pair(n, r));
return r;
}

递归算法复杂度分析

下图取自算法导论

complexAnalysis

STL学习记录:

为了更加优雅的写C++,在学了一点C++17皮毛之后,重新探索了一下C++ STL,总结一些好用的特征。

static_cast<T>, optional<T> 是两个好东西。

等到Codeforces 支持C++20后开始学习C++2x

没有必要关心你自己不用的特征!用的就一定要搞清楚。

以下示例中,凡是Vector类型的a.begin(),a.end()对应的数组类型都可以改成 a,a+n

最大最小值

min,max,minmax 都是参数个数为2,返回的是值。所以不举例了没注意到minmax返回的是pair

min_element,max_element,minmax_element参数都是Vector,且返回的是索引。

1
2
3
4
5
std::cout << *max_element(a.begin(), a.end()) << std::endl;
auto lr = minmax_element(a.begin(), a.end()); //不能取*,因为返回的是pair类型
std::cout << *lr.first << " " << *lr.second << std::endl;
auto[l, r] = minmax_element(a.begin(), a.end()); //自动解析也行
std::cout << *l < " " << *r << std::endl;

累积运算 accumulate (长没关系,有代码补全)

1
2
3
4
5
6
7
8
9
std::vector<int> a{1, 3, 2, 4};
std::cout << accumulate(a.begin(), a.end(), 0) << std::endl; //默认累和
std::cout << accumulate(a.begin(), a.end(), 0, std::plus<int>()) << std::endl; //可选加减乘除
std::cout << accumulate(a.begin(), a.end(), 0, std::minus<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 1, std::multiplies<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 1, std::divides<int>()) << std::endl;
std::cout << accumulate(a.begin(), a.end(), 0, [](auto & x, auto & y) {
return 3 * x + y;
}) << std::endl;

排序

stable_sort 是稳定排序,即不改变原有相互不小于的元素的相对位置

1
2
3
4
5
6
7
8
9
10
std::sort(a.begin(), a.end()); // 默认从小到大排序
std::sort(a.begin(), a.end(), std::less<int>()); // 手动从小到大排序(不一定是int,具体问题具体修改)
std::sort(a.rbegin(), a.end()); // 从大到小排序
std::sort(a.begin(), a.end(), std::greater<int>()); // 从大到小排序
//对于 tuple 和 pair 大小关系都是从按照字典序比较的
std::sort(a.begin(), a.end(), [](int & x, int & y) {
return (x ^ 4) < (y ^ 4); // 位运算的优先级好低呀
});
for (auto & x: a) std::cout << x << " ";
std::cout << std::endl;

集合交并运算

1
2
3
4
5
6
7
std::et<int> x{1, 2, 3};
std::set<int> y{2, 3, 5};
std::set<int> t;
std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::inserter(t, t.begin()));
// 若x,y,t是vector等有push_back 的容器,就可以使用
// set_intersection(x.begin(),x.end(),y.begin(),y.end(),back_inserter(t));
// set_union,set_difference,set_symmetric_difference 等同理

lambda表达式递归写法

1
2
3
4
5
function<int(int, int)> gcd = [ & ](int a, int b) -> int { // 注意最前面不能用auto
return b ? gcd(b, a % b) : a;
};
std::cout << gcd(102, 210) << std::endl;
std::cout << std::__gcd(102, 210) << std::endl;

C++ STL 内建的一些好用的函数

1
2
3
4
5
6
7
8
9
10
11
std::__builtin_parity(uint n):   返回n的二进制1的个数奇偶性
std::__builtin_clz(uint n): 返回n的二进制前置0的个数
std::__builtin_ctz(uint n): 返回n的二进制后置0的个数
std::__builtin_ffs(int n): 返回n的二进制从后往前第一次出现1的位置
std::__lg(int n): 返回log2(n)的整数部分
= std::__builtin_ctz(uint n)+1
std::__builtin_popcount(uint n): 返回n的二进制1的个数,以上函数仅在GCC中有
lowbit(uint n): n&(-n) 返回使得最大的2^i|n // 这个不是内建的
//产生大的随机数
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
*/

To Be Continue…

日常表白zly

如有帮助,烦请资瓷(一块也是爱0.0)