| progress | author |
|---|---|
WIP |
XZirui |
[TOC]
线性基擅长处理异或问题，值域为
特点：第
对于插入的数
- 如果线性基没有第
$i$ 位，就让第$i$ 位为$x$ ，退出 - 否则就令
$x = x \bigoplus a_i$ ，继续操作
操作一次之后，$x$ 的最高位一定会变为
最小值：线性基里的最小值即为异或可得到的最小值。例外情况：线性基可以表示
最大值：从高位向低位考虑，如果目前第
与查询最大值的过程类似。设线性基中有
const int N = 30;
int a[N + 1]; // 线性基数组
bool flag; // 线性基能否表示0
// 插入
void insert(int x) {
for (int i = N; i >= 0; --i) {
if ((x >> i) & 1) {
if (a[i]) {
x ^= a[i];
} else {
a[i] = x;
return;
}
}
}
flag = true; // 最后被分解成原集合里一些数的异或和，说明能表示0
}
// 查询x能否表示为集合中的数的异或和
bool check(int x) {
for (int i = N; i >= 0; --i) {
if ((x >> i) & 1) {
if (!a[i]) {
return false;
}
x ^= a[i];
}
}
return true;
}
// 查询能表示的最大值
// 如果给定参数，就代表查询与x异或的最大值
int query_max(int res = 0) {
for (int i = N; i >= 0; --i) {
res = max(res, res ^ a[i]);
}
return res;
}
// 查询能表示的最小值
int query_min() {
if (flag) {
return 0;
}
for (int i = 0; i <= N; ++i) {
if (a[i]) {
return a[i];
}
}
}
// 查询第k小值
int query(int k) {
int res = 0, cnt = 0;
k -= flag;
if (!k) {
return 0;
}
// 把线性基调整为极小线性无关组
for (int i = 0; i <= N; ++i) {
for (int j = i - 1; j >= 0; --j) {
if ((a[i] >> j) & 1) {
a[i] ^= a[j];
}
}
// 统计线性基里有几个数
if (a[i]) {
++cnt;
}
}
if (k >= (1 << cnt)) {
// k比线性基能表示的数的个数还大
return -1;
}
for (int i = 0; i < cnt; ++i) {
if ((k >> i) & 1) {
res ^= a[i];
}
}
return res;
}给定一张无向图，求从点
一条路径由一条链和一个环组成，可以想到分开处理链和环的部分。
对于环的部分，直接找出图中所有的环，放到线性基里处理即可。对于链的部分，找一条
有两个问题：如何选择链？如果线性基中选择的环不在这条链上也可以吗？
第一个问题，这条链任意选即可。假设有更优的一条链
第二个问题，可以从路径上任意一点引出一条到环上的路径，走过环后沿原路返回，这样路径上的值会被异或两次，对答案无影响。
<--! ## 数论
对于求$\gcd$的和，有： $$ \begin{align} \gcd(i,j)&=\sum\limits_{k\mid \gcd(i,j)}\varphi(k)\ &=\sum\limits_{k\mid i, k \mid j}\varphi(k)\ \end{align} $$ 然后可以通过交换求和顺序继续化简。
例P3768： $$ \begin{align} \sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\sum\limits_{k\mid i, k\mid j} \varphi(k)\ &=\sum\limits_{k=1}^n\varphi(k)k^2\sum\limits_{i=1}^{\left\lfloor \tfrac nk \right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac nk\right\rfloor}ij\ &=\sum\limits_{k=1}^n\varphi(k)\cdot k^2\cdot \frac{\left(\left\lfloor\frac nk\right\rfloor + 1\right)^2\left(\left\lfloor\frac n k\right\rfloor\right)^2} 4 \end{align} $$ 设函数$f(x)=\varphi(x)\cdot x^2\cdot$，因此要求$\sum\limits_{i=1}^n f(i) \cdot \dfrac{(\lfloor\dfrac nk\rfloor + 1)^2(\lfloor\dfrac n k\rfloor)^2} 4$。因为$\mu \ast \mathrm {id} = \varphi$，$\varphi \ast 1=\mathrm {id}$，考虑用杜教筛求和，取$g(x)= x^2$，所以有： $$ \begin{align} S(n) &= \sum\limits_{i=1}^n(g\ast f)(i) - \sum\limits_{i=2}^ni^2S\left(\left\lfloor\frac n i\right\rfloor\right)\ (g\ast f)(i)&=\sum\limits_{d\mid i}f(d)g\left(\frac id\right)=\sum\limits_{d\mid i}\varphi(d) \cdot d^2\cdot\frac {i^2}{d^2}\ &=i^2\sum\limits_{d\mid i}\varphi(d) = i^3\ S(n)&=\sum\limits_{i=1}^ni^3-\sum\limits_{i=2}^ni^2S\left(\left\lfloor\frac n i\right\rfloor\right)=\frac {n^2(n+1)^2}4-\sum\limits_{i=2}^ni^2S\left(\left\lfloor\frac n i\right\rfloor\right) \end{align} $$ 先数论分块，每次分块内部调用杜教筛算$S(n)$。 -->
已知
DP 状态为
Warning
滚动数组优化需要从后向前转移，才能保证每个物品只取一次的条件。
时间复杂度
与 0-1 背包类似，但是每个物品都可以选取无限次。
滚动数组优化： $$ f_j=\max{f_j, f_{j-w_i} + v_i} $$
Warning
这里的滚动数组需要从前向后转移，因为每个物品可以选取无限次，所以从前向后转移可以满足无限次选取的要求。
时间复杂度
与 0-1 背包类似，但是每种物品有
将
无论选择几个当前物品，一定可以把选择个数
将物品拆成
时间复杂度
TODO
时间复杂度
Tip
有时候二进制拆分比单调队列优化快。
只需要多开一维存放第二种价值即可，转移方程基本一致。
有
从“在所有物品中选择”变成了“从当前组中选择”，只需要对每一组做一次 0-1 背包即可。
for (int k = 1; k <= T; ++k) { // 枚举组
for (int i = m; i >= 0; --i) { // 枚举背包容量 滚动数组需要从后向前转移
for (int j = 1; j <= cnt[k]; ++j) { // 枚举组内每个物品
if (i >= w[k][j]) {
dp[i] = max(dp[i], dp[i - w[k][j]] + c[k][j]);
}
}
}
}如果要求可以从第
Warning
转移顺序一定不能搞错，才能保证正确性。
有
可以使用树形背包解决依赖性，要求选择儿子节点时必须选择父亲节点。当附件个数有限时，也可以讨论只买主件或买主件和某些附件。
多开一个数组记录某一个状态是怎么转移过来的。可以用
求装到一定容量时的方案数。
把 DP 方程里的
求最优方案数，需要把
转移：
- 如果
$f_{i,j}=f_{i-1,j}$ 且$f_{i,j}\ne f_{i-1,j-v} + w$ ，这说明该方案不放入第$i$ 个物品更优，$g_{i,j}=g_{i-1,j}$ - 如果
$f_{i,j} \ne f_{i-1,j}$ 且$f_{i,j}= f_{i-1,j-v} + w$ ，这说明该方案放入第$i$ 个物品更优，$g_{i,j}=g_{i-1,j-v}$ - 如果
$f_{i,j}= f_{i-1,j}$ 且$f_{i,j}= f_{i-1,j-v} + w$ ，这说明该方案放不放入都优，$g_{i,j}=g_{i-1,j-v}+g_{i-1,j}$
初值：$f_{0}=0,g_{0}=1$。
背包 DP 可以视为
设一种新的卷积
- 0-1 背包和分组背包可表示成
$dp_i= dp_{i-1} \otimes f_i$ ，其中$f_i$ 的第$w_i$ 项为$c_i$ ，第$0$ 项为$0$ ，其他项均为$-\infty$ - 完全背包类似，$f_i$ 的第
$kw_i$ 项为$kc_i$ （$k\in\mathbb N^+$），第$0$ 项为$0$ ，其他项均为$-\infty$ - 计数型 DP
一个人有
设
在第
- 镜子回答“漂亮”，花
$1$ 天走到下一面镜子，贡献是$\dfrac {p_i} {100} \times (dp_{i + 1} + 1)$ - 镜子回答“不漂亮”，花
$1$ 天走到第$1$ 面镜子，贡献是$\dfrac {p_i}{100}\times (dp_{i+1}+1)$
所以：
$$
\begin{align}
dp_{i}&=\frac {p_i}{100}\times (dp_{i+1}+1) + \left(1- \frac {p_i}{100}\right)\left(dp_{1}+1\right)\
&=\frac {p_i}{100}\times dp_{i+1} + \left(1-\frac {p_i}{100}\right)dp_1 + 1
\end{align}
$$
其中
可以尝试推一下
考虑两个数组的最长上升子序列。
如果用
如果将 DP 过程中状态和值互换，可以得到
把一个序列划分成
设
考虑两个转移点
- 若
$k_{AC} > k$ ，$k_{AB} > k$，则$A$ 比$B$ 更优 - 若
$k_{AC} < k$ ，$k_{BC} < k$，则$C$ 比$B$ 更优
因此，$B$ 一定不优，所以可以只在凸壳上考虑。
对于最优化的 DP，每个点只能由一个最优状态转移而来。如果随着 DP 顺序的推进，每一个点的最优转移点也是单调移动的，那么就具有决策单调性。
设
一个二元函数
在形如
当
考虑维护
直接查找和修改太慢，无法接受，可以用一个队列代替 (j, l, r)。$j$ 表示决策，$l$ 和
之后，从队尾开始检查：
- 如果整个决策都不如
$i$ ，即$f_i + w(i,l_j) \le f_j + w(j,l_j)$ ，就整个删去 - 否则，在当前决策中二分查找，然后将不优的一半删去
最后，将决策
给定一些带有价值的物品，价值可以为负，对于物品的选择有一定的限制，要求最大化 / 最小化权值。
例 P2619 Tree I：
有一张无向带权连通图，每条边是黑色或白色，要找一棵恰好有
首先需要设计一个函数
在一个定值
达到
对于任意一个斜率，最多有一条该斜率的直线与凸壳相切。而且斜率越小，对应的切点的横坐标也最小。只要能求出
下凸壳有一个性质：对于同一斜率
则该截距为
有一个性质：切点上的
因为凸壳上切点处的直线截距一定是所有截距中最小的，因此切点上的
后缀树是一棵压缩字典树，存储的是字符串的所有后缀。
后缀树有以下特点：
- 后缀树上每一条边存储了两个整数
from和to，代表的是文本中$[from, to]$ 的部分 - 从根节点出发走过的任意部分都是原字符串的子串
- 后缀树上有后缀链接，类似 AC 自动机的
fail指针，指向的是后缀的真后缀的位置
Ukkonen构建方法1
Ukkonen算法记录了一个三元组 (active_node, active_edge, active_length)，以及 remainder。
active_node表示当前最长隐式后缀的位置active_edge表示当前最长隐式后缀从active_node出发走向的边active_length表示当前最长隐式后缀的长度remainder表示的是还需要插入多少个后缀
初始时，每条边为 root，然后按照以下规则插入：
- 每次插入操作进行时，如果
remainder为$0$ ，将remainder设置为$1$ - 当向根节点插入时：
-
active_node保持为root -
active_edge被设置为即将插入的新后缀的首字符 -
active_length减$1$
-
- 当分裂一条边并插入新节点时，如果该节点不是当前步骤中第一个插入的节点，从上一个插入的节点创造一个后缀链接指向当前节点
- 当从
active_node不为root的节点分裂边时，沿着后缀链接的方向寻找节点，将该节点设置为active_node
constexpr int N = 1e6+5;
int lnk[N << 1], s[N << 1], len[N << 1], start[N << 1], ch[N << 1][27], rem, now = 1, tail = 1;
int n;
int newnode(int st, int le) {
lnk[++tail] = 1;
start[tail] = st;
len[tail] = le;
return tail;
}
void insert(int x) {
s[++n] = x;
++rem;
for (int last = 1; rem;) {
while (rem > len[ch[now][s[n - rem + 1]]]) {
rem -= len[now = ch[now][s[n - rem + 1]]];
}
int &v = ch[now][s[n - rem + 1]];
int c = s[start[v]+rem - 1];
if (!v || c == x) {
lnk[last] = now;
last = now;
if (!v) {
v = newnode(n, 0x3f3f3f3f);
} else {
break;
}
} else {
int u = newnode(start[v], rem - 1);
ch[u][c] = v;
ch[u][x] = newnode(n, 0x3f3f3f3f);
start[v] += rem - 1;
len[v] -= rem - 1;
v = u;
lnk[last] = v;
last = u;
}
if (now == 1) {
--rem;
} else {
now = lnk[now];
}
}
}