【复习笔记】Week 4 数论及其他
NCC79601
2019-11-11 19:09:36
# DAY 1
## 贪心
贪心是真的恶心，我也只能尽力多见模型。
### 选择不相交区间问题
策略：将每个区间按照 **右端点** 排序。依次枚举每个区间，若当前区间与之前已选的区间发生冲突，则不选；否则选。
```cpp
// https://ac.nowcoder.com/acm/contest/950/A
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010;
struct interval {
int l, r;
bool operator < (const interval &rhs) const {
return r < rhs.r;
}
} a[MAXN];
int n, ans = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d %d", &a[i].l, &a[i].r);
sort(a + 1, a + n + 1);
int pre = 0, i, ans = 0;
for (i = 1; i <= n; i++) {
while (a[i].l < pre && i <= n)
i++;
if (i > n)
break;
// 注意特判一下 i > n 的情况
pre = a[i].r;
ans++;
}
printf("%d", ans);
return 0;
}
```
### 区间选点问题
策略：尽量取区间末尾的点。当一个区间有多个点时，先判断当前区间已经有多少个点，然后再把剩下的点放到区间末尾。
### 区间覆盖问题
策略：将每个区间按照 **左端点** 排序，在能覆盖当前点的区间里尽量选取覆盖得远的区间。
```cpp
// https://ac.nowcoder.com/acm/contest/950/C
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e4 + 10;
int T, n, L, W, tot;
struct interval {
double l, r;
bool operator < (const interval &rhs) const {
return l < rhs.l;
}
} a[MAXN];
int work() {
int ans = 0, i = 1;
double cur = 0;
while (cur < L) {
ans++;
double pre = cur;
while (a[i].l <= pre && i <= n) {
cur = max(cur, a[i].r);
// 寻找能覆盖到的最远边界
i++;
}
if (pre == cur && cur < L)
return -1;
// 无解判断
}
return ans;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &L, &W);
tot = 0;
for (int i = 1, pos, r; i <= n; i++) {
scanf("%d %d", &pos, &r);
if ((r << 1) <= W)
continue;
tot++;
double len = sqrt(r * r - (1.0 * W * W / 4));
a[tot].l = 1.0 * pos - len, a[tot].r = 1.0 * pos + len;
}
n = tot;
sort(a + 1, a + n + 1);
printf("%d\n", work());
}
return 0;
}
```
### 流水作业调度问题
描述：有两台机器$M_1,M_2$，有$n$个任务，任务$i$需要先在$M_1$上耗时$a_i$完成，再在$M_2$上耗时$b_i$完成，求最优的顺序使得完成时间最短。
策略：把$M_1$的工作时间塞满，再尽量把$M_2$等待$M_1$呈递任务的时间、$M_1$完成所有任务以后等待$M_2$的时间缩短。考虑把剩下任务的$a_i,b_i$统一排序。若最小的是$a_i$，则把任务$i$放到剩下任务的第一个完成；若最小的是$b_i$，则把任务$i$放到剩下任务的最后一个完成。这也被称为 Johnson 算法。
在实际操作中，需要的是对任务排序。对于$a_i<b_i$的任务，以$a_i$为关键字升序排序；对于$a_i\geq b_i$的任务，以$b_i$为关键字降序排序。此后，先完成$a_i<b_i$的任务，再完成$a_i\geq b_i$的任务，即可得到最优完成顺序。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
struct node {
int id, a, b;
bool operator < (const node &rhs) const {
if (a < b) {
if (rhs.a < rhs.b)
return a < rhs.a;
else
return true;
} else {
if (rhs.a >= rhs.b)
return b > rhs.b;
else
return false;
}
}
// Johnson 算法核心
} work[MAXN];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &work[i].a);
for (int i = 1; i <= n; i++)
scanf("%d", &work[i].b), work[i].id = i;
sort(work + 1, work + n + 1);
int t1 = 0, t2 = 0;
for (int i = 1; i <= n; i++) {
t1 += work[i].a;
if (t2 < t1)
t2 = t1;
t2 += work[i].b;
// 模拟完成任务
}
printf("%d\n", t2);
for (int i = 1; i <= n; i++)
printf("%d ", work[i].id);
return 0;
}
```
### 带期限与罚款的任务调度问题
策略：尽量完成罚款金额大的任务。排序以后，按顺序枚举任务，尝试在死线前的最晚时间完成任务，使得当前任务的完成对其他任务的影响降到最小；若无法完成，则放弃完成当前任务并上交罚款。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
struct node {
int t, f;
bool operator < (const node &rhs) const {
return f > rhs.f;
}
} a[MAXN];
bool vis[MAXN];
int m, n;
int main() {
scanf("%d\n%d", &m, &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i].t);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i].f);
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
for (int j = a[i].t; j; j--)
if (!vis[j]) {
vis[j] = true;
a[i].f = 0;
break;
}
m -= a[i].f;
}
printf("%d", m);
return 0;
}
```
### 坐船问题
描述：有$n$个人，第$i$个人体重为$w_i$，现有载重量为$m$的小船，每只船最多只能载两个人，问最少需要多少只船才能使所有人过河。
策略：按体重从小到大依次枚举每个人，每次寻找能和当前人共坐一条船的最重的人；无法匹配的则单独坐一条船。
### 树上选链问题
描述：在一棵树上取最多的链使得每根链的长度都大于等于$m$。
策略：从子树出发，考虑对子树做一次反义坐船问题贪心，即：从小到达枚举每条链，每次寻找最小的能和当前链凑在一起的链；最后上传子树中最长的 无法凑出一根符合题意的链 的链。此过程可以用 `multiset` 加速。
```cpp
int dfs(int u, int fa, int lim) {
mset[u].clear();
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to, w = edge[i].w;
if (v == fa)
continue;
int cur = w + dfs(v, u, lim);
if (cur >= lim)
ans++;
else
mset[u].insert(cur);
// 统计所有链
}
int res = 0;
// 核心代码部分：
while (!mset[u].empty()) {
if (mset[u].size() == 1) {
// 特判最后一个没有链匹配的链
res = max(res, *mset[u].begin());
break;
}
it = mset[u].lower_bound(lim - *mset[u].begin());
if (it == mset[u].begin() && mset[u].count(*mset[u].begin()) == 1)
it++;
// 特判找到的匹配链就是当前链的尴尬情况
if (it == mset[u].end()) {
// 也就是无法找到匹配链，则更新上传的 res
res = max(res, *mset[u].begin());
mset[u].erase(mset[u].begin());
continue;
}
ans++;
mset[u].erase(it);
mset[u].erase(mset[u].begin());
// 注意上面两句话的顺序！
// it 可能等于 mset[u].begin()
// 贪心匹配
}
return res;
}
```
## 概率与期望
紧急抱大腿！~~然而考到了还不是做不起~~
一般可以设$f[i]$表示从$i$开始期望还要走$f[i]$步到达终点，$w[i\rightarrow j]$表示从$i$走到$j$对答案的贡献，则有核心表达式：
$$f[i]=\sum(P[i\rightarrow j]\cdot f[j]+w[i\rightarrow j])$$
要考概率期望 dp 估计也就只会考到这个表达式的难度。
### 涂格子问题
#### 问题 1
$n$个格子，每次随机涂一个，求涂满$m$个格子的期望次数。
分析：逆推。用$f[i]$表示涂满$i$个格子的期望步数，最终状态为$f[m]=0$，考虑涂的格子是涂过的还是没有涂过的，则有：
$$f[i]=\frac in\cdot f[i]+\frac {n-i}n\cdot f[i-1]+1$$
#### 问题 2
$n$个格子，每次随机涂一个，求涂$m$次后的期望涂色格子数。
分析：用$f[i]$表示涂$i$次后的期望涂格子数，已知$f[0]=0$，则有：
$$f[i]=\frac{n-f[i-1]}n\cdot (f[i-1]+1)+\frac{f[i-1]}n\cdot f[i-1]$$
化简后可得：
$$f[i]=\frac{n-f[i-1]}n+f[i-1]$$
#### 问题 3
$n$个格子，每次会涂一个格子，其中涂第$i$个格子的概率是$p_i$ $(\sum p_i=1)$，求每个格子都被涂色的期望次数。
分析：只能用状压来做。用$S$表示涂格子的状态，则最终状态为$f[2^n-1]=0$，转化为问题 1，则有：
$$f[S]=\sum_{i=1}^n p_i\cdot f[S|2^{i-1}]+1$$
## 欧拉函数
$\varphi(n)$表示$[1,n-1]$范围内与$n$互质的数的个数。则有：
$$\varphi(n)=n\cdot \prod(1-\frac1{p_i})$$
其中$p_i$为$n$的所有质因子。特殊地，$\varphi(1)=1$。
枚举写法：
```cpp
int phi(int n) {
int res = n;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) {
// 找到质因子
res = res / i * (i - 1);
while (n % i == 0)
n /= i;
// 去除所有质因子
}
if (n > 1)
res = res / n * (n - 1);
// 注意特判最后一个质因子！
return res;
}
```
线性筛写法：
```cpp
void euler() {
for (int i = 1; i <= n; i++)
phi[i] = i;
// 初始化 phi(n) 的值
for (int i = 2; i <= n; i++)
if (phi[i] == i)
for (int j = i; j <= n; j += i)
phi[j] = phi[j] / i * (i - 1);
return ;
}
```
例题：有一个$n\times n$的网格图，求站在$(1,1)$能看到的点数。
分析：把$(1,1)$看作$(0,0)$，也就是说 `n--`。考虑所有能看到的点，可以发现其横纵坐标互质，所以对角线一侧的答案就是$\sum_{i=1}^n\varphi(i)$，而整张图的答案即$2\cdot\sum_{i=1}^n\varphi(n)-2+1$。注意需要特判$(0,1)$和$(1,0)$这两个没有算到的点，以及重复计算了的$(1,1)$。
```cpp
https://www.luogu.org/problem/P2158
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e4 + 10;
int n, phi[MAXN];
void euler() {
for (int i = 1; i <= n; i++)
phi[i] = i;
for (int i = 2; i <= n; i++)
if (phi[i] == i)
for (int j = i; j <= n; j += i)
phi[j] = phi[j] / i * (i - 1);
return ;
}
int main() {
scanf("%d", &n);
if (n == 1) {
putchar('0');
return 0;
}
// 注意特判 n = 1 的情况
n--;
euler();
long long ans = 2;
// 预先计算 (0, 1) 以及 (0, 1)
for (int i = 1; i <= n; i++)
ans += phi[i] << 1;
printf("%lld\n", ans - 1);
// 减去重复计算的 (1, 1)
return 0;
}
```
### 欧拉定理
若$\gcd(a,n)=1$，则有：
$$a^{\varphi(n)}\equiv 1(\mod n)$$
运用这个性质也可以推出费马小定理，即当$\gcd(a,p)=1$且$p$为质数，有：
$$a^{\varphi(p)}=a^{p-1}\equiv 1\Rightarrow a^{-1}=a^{p-2}(\mod p)$$
## 二分
用于 **最大值最小**，**最小值最大**，以及无法确定边界的题目（当然也不一定全都是用二分来写）。核心在于 `check()` 函数。
容易错的地方：
1. `l = mid + 1` 以及 `r = mid - 1` 的判断；
2. 边界值的判断。
这里还有一种无论何种情况都不会出错的二分写法，也就是说用 `mid` 来更新 `ans`，然后 `l = mid + 1` 或者 `r = mid - 1` 以缩小二分范围。
```cpp
int my_binary_search() {
int l = 1, r = up, ans;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid))
l = mid + 1, ans = mid;
else
r = mid - 1;
}
return mid;
}
```
# DAY 2
## 扩展欧几里得
裴蜀定理：$ax+by=\gcd(a,b)$ 一定有整数解。当然，两边同乘整数后的不定方程也一定有解。
考虑如何求解这个不定方程：
$$\gcd(a,b)=\gcd(b,a\%b)$$
$$\Rightarrow ax+by=bx_0+(a\%b)y_0$$
设 $/$ 表示整除，原式恒等，则有：
$$ax+by=bx_0+(a-a/b\cdot b)y_0$$
$$ax+by=ay_0+b\cdot(x_0-a/b\cdot y_0)$$
$$\Rightarrow\left\{\begin{aligned}&x=y_0,\\&y=x_0+a/b\cdot y_0\end{aligned}\right.$$
考虑如何求通解。设 $k\in\text{Z}$，假设已经有一组解$(x_0,y_0)$满足 $ax_0+by_0=\gcd(a,b)$，则：$(x_1,y_1)=(x_0+k\cdot b,y_0-k\cdot a)$ 也是满足解的。不过为了保证 $x_1,y_1\in \text{Z}$，所以$k\cdot b,k\cdot a\in \text{Z}$。合情推理，可知通解为：
$$\left\{\begin{aligned}&x=x_0+k\cdot\frac b{\gcd(a,b)},\\&y=y_0-k\cdot\frac a{\gcd(a,b)}\end{aligned}\right.$$
不过需要注意的是，设$ax+by=\gcd(a,b)$的一组解为$(x_0,y_0)$，对于不定方程$ax+by=k\cdot\gcd(a,b)$的通解$(x,y)$，其$x,y$的增减量仍然满足$\Delta x=\Delta x_0,\Delta y=\Delta y_0$，而$x,y$的基数则变为原来的$k$倍，并且在 `exgcd()` 过程中不能把$x,y$取模（最后需要对$\Delta x,\Delta y$取模）。这里的处理方法 **非常容易出错**。
```cpp
void exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1, y = 0;
return ;
}
ll x_0, y_0;
exgcd(b, a % b, x_0, y_0);
x = y_0;
y = x_0 - a / b * y_0;
// 不 取 模
return ;
}
int main() {
// ax + by = c
ll x, y, delta;
exgcd(a, b, x, y);
x *= c / gcd;
delta = b / gcd;
x = (x % delta + delta) % delta;
// x + k * delta 即为 x 的通解
return 0;
}
```
例题：给定四个正整数$a,b,c,k$，回答是否存在一个正整数$n$，使得 $a\cdot n$ 在$k$进制表示下的各位的数值之和模$b$为$c$。
分析：若$k\rightarrow+\infty$，则数字之和即$a\cdot n$；否则，一次进位对数字之和的贡献为$1-k$，所以整个问题转化为判断：
$$a\cdot x+(1-k)\cdot y\equiv c(\mod b)$$
$$\Rightarrow a\cdot x+(1-k)\cdot y+b\cdot z=c$$
上述方程有解，所以运用裴蜀定理即可。
```cpp
// https://ac.nowcoder.com/acm/problem/15699
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
printf((c % gcd(gcd(a, b), k - 1)) ? "No\n" : "Yes\n");
}
return 0;
}
```
## 逆元
逆元的递推求法：设$p=k\cdot i+r$，则有：
$$k\cdot i+r\equiv0(\mod p)$$
两边同乘$i^{-1}$和$r^{-1}$，则有：
$$k\cdot r^{-1}+i^{-1}\equiv0(\mod p)$$
$$\begin{aligned}\\\Rightarrow\;&i^{-1}\equiv -k\cdot r^{-1}&(\mod p)\\\Rightarrow\;& i^{-1}\equiv(p-p/i)\cdot r^{-1}&(\mod p)\end{aligned}$$
也就是说可以根据这个式子进行递推了。
### 一个小结论
若$a=k\cdot b(k\in \text{Z}^*)$，则：
$$a/b\%c=a\%(b\times c)/b$$
这个结论适用于 $b$ 在$\mod c$ 意义下不存在逆元的情况。
# DAY 3
## 矩阵
设$f_n$为斐波那契数列第$n$项，有这样一个性质：
$$\left[\begin{matrix}1&1\\1&0\end{matrix}\right]^{n}=\left[\begin{matrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{matrix}\right]$$
## 卡特兰数
通项公式：
$$c_n=C_{2n}^n-C_{2n}^{n-1}=\frac1{n+1}\cdot C_{2n}^n$$
卡特兰数的前几项：$1,1,2,5,14,42,132,429\cdots$
考场上打个表，看到前几项差不多就直接盲猜卡特兰数吧。
## 中国剩余定理
求解线性同余方程组：
$$\begin{aligned}x&\equiv a_1(\mod m_1)\\x&\equiv a_2(\mod m_2)\end{aligned}$$
$$\cdots$$
$$\begin{aligned}x&\equiv a_n(\mod m_n)\end{aligned}$$
定理：若$m_1,m_2,\cdots,m_n$两两互质，则方程组有整数解。
设$M=\prod_{i=1}^n m_i$，且$M_i=\frac M{m_i}$，$M_i^{-1}$为$M_i$在模$m_i$意义下的逆元；则方程组在模$M$意义下有最小整数解：
$$x\equiv \sum_{i=1}^n a_i\cdot M_i\cdot M_i^{-1}(\mod M)$$
计算过程中，可以使用 exgcd 求得逆元。
```cpp
ll CRT() {
ll x, y;
for (int i = 1; i <= n; i++) {
ll Mi = M / m[i];
exgcd(Mi, m[i], x, y);
ans = (ans + a[i] * Mi * x) % M;
}
return ans;
}
```
## 组合数
### 杨辉三角
组合数的递推可以用杨辉三角实现。
$$\begin{aligned}1\\1&&1\\1&&2&&1\\1&&3&&3&&1\\1&&4&&6&&4&&1\end{aligned}$$
$$\cdots$$
需要注意的是：杨辉三角的横纵坐标都是从$0$开始编号。
```cpp
void prework() {
memset(C, 0, sizeof(C));
// 清 0 防出锅
C[0][0] = 1;
for (int i = 1; i <= 2000; i++) {
C[i][0] = 1;
for (int j = 1; j <= 2000; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
return ;
}
```
### 卢卡斯定理
这个直接记就好了，反正又不太可能会考。
$$C^n_m\equiv C^{n/p}_{m/p}\cdot C^{n\%p}_{m\%p}(\mod p)$$
需要注意的是，这里可能会用到预处理阶乘 + 逆元来计算$C_n^m$。
# DAY 4
## KMP 匹配
KMP 匹配的核心思想是利用模式串的类回文性质以加速失配以后的移动。`kmp[i]` 数组的意义是第$i$位失配以后应该跳转到模式串的哪个位置。在预处理 `kmp[i]` 的时候可以使用模式串自我匹配的方法。
背背板子应该就够了。
```cpp
// https://www.luogu.org/problem/P3375
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int kmp[MAXN];
int l1, l2, j;
char a[MAXN], b[MAXN];
int main() {
scanf("%s", a + 1);
scanf("%s", b + 1);
l1 = strlen(a + 1), l2 = strlen(b + 1);
j = 0;
for (int i = 2; i <= l2; i++) {
// 注意是从 2 开始
while (j && b[i] != b[j + 1])
j = kmp[j];
if (b[i] == b[j + 1])
j++;
kmp[i] = j;
}
// 自我匹配以生成 kmp[] 数组
j = 0;
for (int i = 1; i <= l1; i++) {
while (j && a[i] != b[j + 1])
j = kmp[j];
// 失配后依靠 kmp[] 进行跳转
if (a[i] == b[j + 1])
j++;
if (j == l2) {
// 匹配成功
printf("%d\n", i - l2 + 1);
j = kmp[j];
}
}
for (int i = 1; i <= l2; i++)
printf("%d ", kmp[i]);
return 0;
}
```
## 博弈论
再次紧急抱大腿！
P 状态：先手必败（**P**re wins）
N 状态：先手必胜（**N**ow wins）
博弈树：由状态和合法移动构成的树。考虑博弈树上点的性质：
1. 一个 N 节点的儿子中一定有一个 P 节点；
2. 一个 P 节点的儿子一定都是 N 节点；
3. 没有儿子的节点一定是 P 节点。
根据这个性质，在建博弈树的时候，先把所有叶子节点标记为 P 节点，然后向上递归即可。
博弈树可能会用到 LCA 以及树的许多性质。
### Nim 游戏
有$n$堆石子（每堆石子数量小于$10000$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取；每次只能从一堆里取。最后没石子可取的人落败。已知每堆石子的数量，问是否存在先手必胜的策略。
结论：设第$i$堆石子数为$a_i$，则若$a_1\otimes a_2\otimes\cdots\otimes a_n\not ={0}$，先手必胜；若$a_1\otimes a_2\otimes\cdots\otimes a_n=0$，则先手必败。
分析：显然，$\forall a_i=0$的局面是先必败的，此时异或和为$0$；在其他情况下，先手只要把异或和变为$0$即可使后手永远面对异或和为$0$的情况，直到后手落败。
### 阶梯 Nim 游戏
有$n$级阶梯，$n$级在左右边且最高，地面为$0$，第$i$级阶梯上有$w_i$个石子，两人轮流操作，每次操作可以选择第i级阶梯的若干个石子移动到任意位置（只移动到$i-1$的问题与此题结论相同），最后无法再移动石子的人落败。已知每个阶梯上的石子数量，问是否存在先手必胜的策略。
分析：等价于奇数级上的 Nim 游戏。若奇数级上的 Nim 游戏存在必胜状态，考虑把奇数级的石子移到偶数级当成丢掉石子；若对手把偶数级上的石子移到奇数位，就把那堆石子再移到偶数级上，使对手面对相同的状态。反复按照这个策略进行即可获胜。
### SG 函数
#### $\text{mex}$ 运算
对于集合，$\text{mex}$可以求出未出现在集合中的最小非负整数。而对于一个节点的 SG 函数值的定义为：
$$sg(x)=\text{mex}\{sg(y)|y\in x\text{的后继节点}\}$$
#### 性质
1. 所有叶子结点的 SG 值为$0$；
2. 若$sg(x)=0$，则$x$所有后继节点的 SG 值都不为$0$；
3. 若$sg(x)\not ={0}$，则$x$必有一个后继节点$y$满足$sg(y)=0$。
#### 结论
把原游戏分解成多个独立的子游戏，则原游戏的 SG 函数值是它的所有子游戏的 SG 函数值的异或和。当游戏的 SG 函数异或和为$0$，先手必败。
可以联系博弈树上的 N - P 关系理解：一个节点$x$为 P 节点，则其$sg(x)=0$。
#### SG 值的计算方法
可选步数为$1\sim m$ 的连续整数，$sg(x)=x \mod (m+1)$；
可选步数为任意步，$sg(x)=x$；
可选步数没有规律，暴力计算。
# DAY 5
考前最后一天了。
$\text{\large「无数时间线，无尽可能性，终于交织向你。」}$