0%

背包问题

有N个物品 和 容量为的背包
每个物品有两个属性 体积Vi,价值Wi

01背包

每件物品只能用一次

01背包思路

01背包题目
答案
优化版答案

完全背包

每件物品有无限个

完全背包思路

题目
朴素做法

优化思路

优化做法

终极写法

多重背包

每件物品有s件

题目

朴素做法

优化版本

分组背包

N组物品,每一组有若干个

思路

20220202154520

线性DP

20220204142023

20220204142833

20220204151448
20220204151347

区间DP

20220204153722

计数类DP

数位统计DP

状态压缩DP

树形DP

记忆化搜索

组合数

20220130161127

递推法求组合数

10w组询问, 1<=b<=a<=2000
O(N^2)
先预处理

20220130162159

1
2
3
4
5
6
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

通过预处理逆元的方式求组合数

10w组询问, 1<=b<=a<=1e5

O(logn)
20220130164210

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
首先预处理出所有阶乘取模的余数fact[N],以及所有阶乘取模的逆元infact[N]
如果取模的数是质数,可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}

// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}


Lucas定理

20组询问, 1<=b<=a<=1e18
o(P * logN * logP)
20220130170307

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
若p是质数,则对于任意整数 1 <= m <= n,有:
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)

int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}

int C(int a, int b, int p) // 通过定理求组合数C(a, b)
{
if (a < b) return 0;

LL x = 1, y = 1; // x是分子,y是分母
for (int i = a, j = 1; j <= b; i --, j ++ )
{
x = (LL)x * i % p;
y = (LL) y * j % p;
}

return x * (LL)qmi(y, p - 2, p) % p;
}

int lucas(LL a, LL b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}


分解质因数法求组合数

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
当我们需要求出组合数的真实值,而非对某个数的余数时,分解质因数的方式比较好用:
1. 筛法求出范围内的所有质数
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
3. 用高精度乘法将所有质因子相乘

int primes[N], cnt; // 存储所有质数
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否已被筛掉


void get_primes(int n) // 线性筛法求素数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}


int get(int n, int p) // 求n!中的次数
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}


vector<int> mul(vector<int> a, int b) // 高精度乘低精度模板
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}

while (t)
{
c.push_back(t % 10);
t /= 10;
}

return c;
}

get_primes(a); // 预处理范围内的所有质数

for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘
for (int j = 0; j < sum[i]; j ++ )
res = mul(res, primes[i]);


卡特兰数

1
2
给定n个0和n个1,它们按照某种顺序排成长度为2n的序列,满足任意前缀中0的个数都不少于1的个数的序列的数量为: Cat(n) = C(2n, n) / (n + 1)

高斯消元

用来解方程

20220130153207

20220130154007

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
// a[N][N]是增广矩阵
int gauss()
{
int c, r;
for (c = 0, r = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ ) // 找到绝对值最大的行
if (fabs(a[i][c]) > fabs(a[t][c]))//比较绝对值
t = i;

if (fabs(a[t][c]) < eps) continue;

for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];

r ++ ;
}

if (r < n)
{
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps)
return 2; // 无解
return 1; // 有无穷多组解
}

for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];

return 0; // 有唯一解
}


NIM游戏 —— 模板题 AcWing 891. Nim游戏

给定N堆物品,第i堆物品有Ai个。两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可把一堆取光,但不能不取。取走最后一件物品者获胜。两人都采取最优策略,问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手,第二个行动的称为后手。若在某一局面下无论采取何种行动,都会输掉游戏,则称该局面必败。
所谓采取最优策略是指,若在某一局面下存在某种行动,使得行动后对面面临必败局面,则优先采取该行动。同时,这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况,即两人均无失误,都采取最优策略行动时游戏的结果。
NIM博弈不存在平局,只有先手必胜和先手必败两种情况。

定理: NIM博弈先手必胜,当且仅当 A1 ^ A2 ^ … ^ An != 0

Nim游戏

20220131215546

公平组合游戏ICG

若一个游戏满足:

  1. 由两名玩家交替行动;
  2. 在游戏进程的任意时刻,可以执行的合法行动与轮到哪名玩家无关;
  3. 不能行动的玩家判负;
    则称该游戏为一个公平组合游戏。
    NIM博弈属于公平组合游戏,但城建的棋类游戏,比如围棋,就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子,胜负判定也比较复杂,不满足条件2和条件3。

有向图游戏

给定一个有向无环图,图中有一个唯一的起点,在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动,每次可以移动一步,无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是,把每个局面看成图中的一个节点,并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算,即:
mex(S) = min{x}, x属于自然数,且x不属于S

SG函数

在有向图游戏中,对于每个节点x,设从x出发共有k条有向边,分别到达节点y1, y2, …, yk,定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果,即:
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地,整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值,即SG(G) = SG(s)。

有向图游戏的和 —— 模板题 AcWing 893. 集合-Nim游戏

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G,它的行动规则是任选某个有向图游戏Gi,并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和,即:
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

定理

有向图游戏的某个局面必胜,当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败,当且仅当该局面对应节点的SG函数值等于0。

裴蜀定理

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
// 求x, y,使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}

快速幂

快速的求a^k mod p

20220129211626

1
2
3
4
5
6
7
8
9
10
11
12
13
14
求 m^k mod p,时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}

欧拉函数

1-n中,与n互质(两个数的公因数只有1)的数的个数,即 φ(N)

20220128211849

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);

return res;
}


筛法求欧拉函数

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

int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉


void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}


质数

质数:严格大于1,从2开始,只包含1和本身这两个约数,就是质数或者素数

质数的判定 (试除法)

1
2
3
4
5
6
7
8
9
10
11
12
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
{
if (x % i == 0)
return false;
}
return true;
}


分解质因数 (试除法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
{
if (x % i == 0)
{
int s = 0;
while (x % i == 0)
{
x /= i;
s ++ ;
}
cout << i << ' ' << s << endl;
}
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}

朴素(埃氏)筛法求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int primes[N], cnt;     // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}

线性筛法求素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int primes[N], cnt;     // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉

void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;//primes[j]一定是i的最小质因子
if (i % primes[j] == 0) break;
}
}
}

约数

试除法求约数

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}

约数个数和约数之和

1
2
3
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数: (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和: (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

求所有数乘积的约数个数

求所有数乘积的约数之和

欧几里得算法 (辗转相除法)

求最大公约数

1
2
3
4
5

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}