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

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

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

C++ 代码规范

此规范参考:Codeforces 上 Jiangly 的码风,Menci 代码规范,知乎 pansz 的回答
VSCode 的 C_Cpp: Clang_format_style 设置为:{ BasedOnStyle: google, IndentWidth: 4,TabWidth: 4, UseTab: Always, BreakBeforeBraces: Custom, AllowShortIfStatementsOnASingleLine: true, IndentCaseLabels: false }

设置可参考:官方代码风格配置

总纲

  • 不再使用 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
55
56
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
#define println std::cout << 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 = std::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 的使用

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;
}

交互式题目模板

gym101021: Guess the Number
需要 fflush(stdout); 来刷新缓冲区,不过 std::endl 会自动刷新一次缓冲区,所以此时可以省略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;

int main() {
//freopen("in","r",stdin);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int l = 1, r = 1e6;
while (l <= r) {
int m = (l + r) / 2;
std::cout << m << std::endl;
std::string s;
std::cin >> s;
if (s[0] == '<') r = m - 1;
else l = m + 1;
}
std::cout << "! " << r << std::endl;
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
const int N = 1e9 + 9;
bool isp[N];
std::vector<int> p;

void initPrimeP() {
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 = 1, 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;
}
}
}

欧拉线性素数筛(正式使用版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 1e9 + 9;
bool isp[N];
std::vector<int> p;
int initPrimeP() {
p.emplace_back(2);
isp[2] = true;
for (int i = 3; i < N; i += 2) isp[i] = true;
int sq = int(std::sqrt(N - 1))|1;
for (int i = 3; i <= sq; i += 2) if (isp[i]) {
p.emplace_back(i);
for (int j = i * i; j < N; j += i << 1) {
isp[j] = false;
}
}
for (int i = sq + 2; i < N; i += 2) if (isp[i]) p.emplace_back(i);
return p.size();
}

大素数 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 \mid 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;
}

注意到,矩阵乘法一定要写成上面的循环形式,这样利用高速缓存执行时间是原有的 $\frac{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 开始)

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
struct TreeArray {
std::vector<LL> s;
TreeArray() {}
TreeArray(int n) { init(n); }
void init(int n) {
s.resize(n + 1);
std::fill(s.begin(), s.end(), 0);
}
int lowbit(int n) {
return n & (-n);
}
void add(int id, int p) {
while (id < s.size()) {
s[id] += p;
id += lowbit(id);
}
}
LL sum(int id) {
LL r = 0;
while (id) {
r += s[id];
id -= lowbit(id);
}
return r;
}
// find minimal index s.t. sum(id) >= x, sum must be increased
int search(LL val) {
LL sum = 0;
int id = 0;
for (int i = std::__lg(s.size()); ~i; --i) {
if (id + (1 << i) < s.size() && sum + s[id + (1 << i)] < val) {
id += (1 << i);
sum += s[id];
}
}
return ++id;
}
};

树状数组(区间更新,区间求和,编号从 1 开始)

有了单点更新的树状数组,只需简单利用差分就可以变成区间的更新了。
设原始数组为 a[1 ~ n], 定义 c[i] = a[i] - a[i - 1], (a[0] = 0) 显然

比如对区间 [l, r] 做更新,那么就只需更新两点:r + 1, l ,套用之前的类就行了。

注意在树状数组中搜索本来应该是 $O(\log ^2 n)$,但是因为在 $2^i$ 的位置搜索时,一步到位。所以复杂度会降到 $O(\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
struct TreeArray2 {
int n;
TreeArray B, C;
TreeArray2() {}
TreeArray2(int _n) : n(_n){
B.init(n);
C.init(n);
}
void add(int id, int p) {
C.add(id, p);
B.add(id, (id - 1) * p);
}
void add(int l, int r, int p) {
add(l, p);
if (r + 1 < n) add(r + 1, -p);
}
LL sum (int id) {
return id * C.sum(id) - B.sum(id);
}
// find minimal index s.t. sum(id) >= x, sum must be increased
int search(LL val) {
LL sumB = 0, sumC = 0;
int id = 0;
for (int i = std::__lg(n); ~i; --i) if (int idi = id + (1 << i); idi <= n) {
if (idi * (sumC + C.s[idi]) - B.s[idi] - sumB < val) {
id = idi;
sumB += B.s[id];
sumC += C.s[id];
}
}
return ++id;
}
};

线段树

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
15
16
class LinkStar {
public:
std::vector<int> head, nxt, to;
std::vector<LL> w;
LinkStar(int n) {
nxt.clear();
to.clear();
head = std::vector<int>(n + 1, -1);
}
void addedge(int u, int v, LL val) {
nxt.emplace_back(head[u]);
head[u] = to.size();
to.emplace_back(v);
w.emplace_back(val);
}
};

知乎上看到 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;
}

树的直径:先从任意点开始寻找最远距离点(bfs 遍历一下),然后再找一次就是了(易证)

例题:1405D

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

OI - wiki 中看到的讲解和复杂度分析!,注意到右链是从尾巴往上查找的。
hdu 1506
这就给出了一个 $O(n)$ 复杂度求出包含 i且以 a[i] 为最小值的区间的方法,太强了!
求上述对应的最大值区间,需要修改 0 节点的值,以及 build 的大于号改成小于号。

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
#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
#define print(x) std::cout << (x) << std::endl
using LL = long long;
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, 1e9 + 2, 0);
for (int i = 1, x; i <= n; ++i) {
std::cin >> x;
tree[i].init(i, x, 0);
}
int root = cartesian_build(tree, n);
LL ans = 0;

std::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 = std::max(ans, LL(sz + 1) * tree[x].val);
return sz + 1;
};
dfs(root);
std::cout << ans << std::endl;

// 下面是求以 a[i] 为最小值且包含 i 的最大区间
int l[n + 1], r[n + 1];
std::function<void(int)> getinterval = [&](int x) {
if (x == 0) return;
if (tree[tree[x].par].ch[0] == x) {
r[x] = tree[x].par - 1;
l[x] = l[tree[x].par];
} else {
l[x] = tree[x].par + 1;
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]);
// 要考虑有相同值的情形,必须要分两次搞,不然有bug
std::function<void(int)> updateinterval = [&](int x) {
if (x == 0) return;
if (tree[tree[x].par].ch[0] == x) {
if (tree[x].val == tree[tree[x].par].val) r[x] = r[tree[x].par];
} else {
if (tree[x].val == tree[tree[x].par].val) l[x] = l[tree[x].par];
}
updateinterval(tree[x].ch[0]);
updateinterval(tree[x].ch[1]);
};
updateinterval(tree[root].ch[0]);
updateinterval(tree[root].ch[1]);
for (int i = 1; i <= n; ++i) {
std::cout << l[i] << " " << r[i] << std::endl;
}
}
return 0;
}

洛谷 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