【线性代数】矩阵乘法与线性DP优化
前言
现在有一道题目如下：
概念
什么是矩阵（matrix）
下面是一个$2 \times 2$的矩阵，其中
$$\begin{bmatrix}{a} & {b} \ {c} & {d}\end{bmatrix}$$
关于矩阵的其他内容我们不再延申，你现在只要知道矩阵是这么样的一个东西就可以了。
矩阵可以用字母代表，那么矩阵 $A_{n \times m}$ 本质上是一个 n 行 m 列的二维数组。
矩阵乘法
矩阵之间可以相乘，并且满足结合律与分配律——不满足交换律，在$n \times m(n \ne m)$这种不是
$$ C*{n\times s}=A*{n\times m}:\times B_{m\times s} $$
那么它实际上就等于：
$$ C*{ij}=\sum A*{ik}\times B_{kj}\left(1:\le:k:\le:m\right) $$
其中 k 的遍历过程也就是
写成代码形式，就和弗洛伊德很像，可以把弗洛伊德看成是魔改的矩阵乘法：
用矩阵优化线性 DP
回到前言我们说的题目，这里回顾一下：
$$ \left[{f_{i-1}},:f_{i-2}\right]\times\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]=\left[{f_i},:f_{i-1}\right] $$
因为是线性的，所以我们很容易发现，每一转移其实就是当前的状态矩阵乘上我们的$\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]$，那么每转移一次，i 就加一，我们先处理出$f_1,f_2$，那么通过$n-2$次转移，我们就可以得到$f_n$的值。
延伸
所有类似于这样的线性 DP 都可以用矩阵来转移，比如$f_i = f_{i-1} + f_{i-3} + f_{i-4}$，这种转移，我们可以构造下面这一个转移矩阵：
$$ \begin{bmatrix}1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1\end{bmatrix} $$
然后使用快速幂可以把时间复杂度从$O(N)$优化到$O(k^3 \log N)$ ，其中 k 是状态是数量，也就是转移矩阵的边长。
下面是实例代码，可以解决$f_i = f_{i-1} + f_{i-3} + f_{i-4}$求解$f_n$并且$n \leq 10^{18}$的情况。
via サン猫の時間漂流
前言
现在有一道题目如下：
输入一个整数 n ($n \leq 10^{18}$)， 求第 n 个斐波那契数。众所周知斐波那契数列的递推公式是：$f_i = f_{i-1} + f_{i-2}$。通过$O(N)$的时间递推可以在 1s 内求出前 1e8 的斐波那契数，但是题目的范围是 1e18，这要怎么办呢？这时候就要引出我们今天要学习的内容——矩阵与矩阵乘法了。
概念
什么是矩阵（matrix）
下面是一个$2 \times 2$的矩阵，其中
a，b，c，d，是里面的元素，矩阵里的元素可以是数字符号或者数学式。$$\begin{bmatrix}{a} & {b} \ {c} & {d}\end{bmatrix}$$
关于矩阵的其他内容我们不再延申，你现在只要知道矩阵是这么样的一个东西就可以了。
矩阵可以用字母代表，那么矩阵 $A_{n \times m}$ 本质上是一个 n 行 m 列的二维数组。
矩阵乘法
矩阵之间可以相乘，并且满足结合律与分配律——不满足交换律，在$n \times m(n \ne m)$这种不是
正方形的矩阵中，交换前后两个矩阵相乘会导致结果矩阵的形状不同，我们会在后面解释。矩阵相乘时，相乘矩阵的宽高必须有一个相同，否则无法配对。比如下面这个式子，把矩阵$A \times B = C$，可以这样写：
$$ C*{n\times s}=A*{n\times m}:\times B_{m\times s} $$
那么它实际上就等于：
$$ C*{ij}=\sum A*{ik}\times B_{kj}\left(1:\le:k:\le:m\right) $$
其中 k 的遍历过程也就是
相乘矩阵的宽高必须有一个相同的原因，否则匹配不了。写成代码形式，就和弗洛伊德很像，可以把弗洛伊德看成是魔改的矩阵乘法：
for(int i = 1; i <= an; i++)
for(int k = 1; k <= am; k++)
for(int j = 1; j <= bm; j++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];
用矩阵优化线性 DP
回到前言我们说的题目，这里回顾一下：
输入一个整数 n ($n \leq 10^{18}$)， 求第 n 个斐波那契数。我们每一次转移可以用一个矩阵表示：
$$ \left[{f_{i-1}},:f_{i-2}\right]\times\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]=\left[{f_i},:f_{i-1}\right] $$
因为是线性的，所以我们很容易发现，每一转移其实就是当前的状态矩阵乘上我们的$\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]$，那么每转移一次，i 就加一，我们先处理出$f_1,f_2$，那么通过$n-2$次转移，我们就可以得到$f_n$的值。
延伸
所有类似于这样的线性 DP 都可以用矩阵来转移，比如$f_i = f_{i-1} + f_{i-3} + f_{i-4}$，这种转移，我们可以构造下面这一个转移矩阵：
$$ \begin{bmatrix}1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1\end{bmatrix} $$
然后使用快速幂可以把时间复杂度从$O(N)$优化到$O(k^3 \log N)$ ，其中 k 是状态是数量，也就是转移矩阵的边长。
下面是实例代码，可以解决$f_i = f_{i-1} + f_{i-3} + f_{i-4}$求解$f_n$并且$n \leq 10^{18}$的情况。
这里因为乘的顺序不一样（交换了），矩阵不能使用交换律，所以转移矩阵稍有不同。（实际上一般情况下习惯把系数放在第一行，也就是代码中转移矩阵的样子）
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;
matrix multiply(matrix a, matrix b, ll mod)
{
ll n = a.size();
matrix c(n, vector<ll>(n));
for (ll i = 0; i < n; i++)
for (ll j = 0; j < n; j++)
for (ll k = 0; k < n; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
return c;
}
matrix matrix_pow(matrix a, ll n, ll mod)
{
ll m = a.size();
matrix res(m, vector<ll>(m));
for (ll i = 0; i < m; i++)
res[i][i] = 1;
while (n)
{
if (n & 1)
res = multiply(res, a, mod);
a = multiply(a, a, mod);
n >>= 1;
}
return res;
}
int main()
{
matrix a = {{1, 0, 1, 1},
{1, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 1, 0}}; // 转移矩阵
ll n;
scanf("%lld", &n); // 2, 4, 6, 9
matrix ans = matrix_pow(a, n - 4, 10007);
printf("%lld", (ll)(2 * ans[0][3] + 4 * ans[0][2] + 6 * ans[0][1] + 9 * ans[0][0]) % 10007);
return 0;
}
via サン猫の時間漂流
【题解】7月11日比赛题解备份
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
typedef long long LL;
LL calcfac(LL n)
{
if (n <P) return fac[n];
LL seg = n / P, rem = n % P;
LL ret = power(fac[P - 1], seg, P); //fac[P - 1]重复出现了seg次
ret = ret * fac[rem] % P; //除去seg次fac[P – 1]外，剩下的零头
cnt += n / P; //提出n / P个因子P
ret = ret * calcfac(n / P) % P; //递归处理
return ret;
}
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
【图论】双连通分量
前言
在学习双连通分量之前请先了解强连通分量，有助于理解双连通分量，其中相同的概念不再赘述。
概念
强连通分量是对于有向图而言的，而双连通分量是对于无向图而言的。
割边与割点
在无向图中， 割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。 割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。 割点与割边的关系：
1. 有割点不一定有割边，有割边一定有割点。
2. 割边的两个端点中一定有一个是割点。
什么是双连通分量
根据上面割边与割点的定义，我们可以把双连通分量分成边双和点双两种。
1. 边双：对于一个图，假如仅仅对于该图而言其中没有割边，那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边，每一个点之间仍然是连通的。
2. 点双：对于一个图，假如仅仅对于该图而言其中没有割点，那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边，每一个点之间仍然是连通的。
求双连通分量
先观察
via サン猫の時間漂流
前言
在学习双连通分量之前请先了解强连通分量，有助于理解双连通分量，其中相同的概念不再赘述。
我的强连通分量笔记在：【图论】强连通分量
概念
强连通分量是对于有向图而言的，而双连通分量是对于无向图而言的。
割边与割点
在无向图中， 割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。 割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。 割点与割边的关系：
1. 有割点不一定有割边，有割边一定有割点。
2. 割边的两个端点中一定有一个是割点。
详细内容请阅读：【图论】割边与割点
什么是双连通分量
根据上面割边与割点的定义，我们可以把双连通分量分成边双和点双两种。
1. 边双：对于一个图，假如仅仅对于该图而言其中没有割边，那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边，每一个点之间仍然是连通的。
2. 点双：对于一个图，假如仅仅对于该图而言其中没有割点，那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边，每一个点之间仍然是连通的。
需要注意的是点双与强连通分量和边双不同，它会与其他点双相交，需要注意
求双连通分量
先观察
via サン猫の時間漂流
【数据结构】邻接表与链式前向星
邻接表（使用 vector）
存图方式
遍历方式
添加方式
----------------------
链式前向星
存图方式
遍历方式
添加方式
via サン猫の時間漂流
邻接表与链式前向星更正： 使用vector存图的叫做邻接表使用数组模拟的叫做链式前向星
邻接表（使用 vector）
使用邻接表的优劣： 优势：
1. 码量少，易操作
2. 不用担心空间，不易写错
劣势：
1. cpp11 之前不能使用auto v : i形式遍历 vector
2. 在不能开启O2的题目中较慢（POJ 全占）
存图方式
struct line // 自定义结构体
{
int ver; // 指向的结点
int edge; // 边的权值
line(int v, int e) // 构造函数
{
ver = v;
edge = e;
}
};
vector<line> g[MAX]; // 新建邻接表
遍历方式
对于 C++11 后的 OJ，使用如下方式遍历：
// line是结构体的名字
// from是父节点的下标
for(line son : g[crd])
{
// 示例代码，含义为不经过父节点
if(son.ver == from) continue;
}
对于 C++11 前的 OJ，使用如下方式遍历其实这里建议使用链式前向星，因为不支持 C++11 的 OJ 很可能没有 O2
// line是结构体名字
for (line son = g.begin(); son != g.end(); son++)
// 下略……
添加方式
// N为边的数量
for(int i = 1; i < N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(line(v, w));
g[v].push_back(line(u, w));
}
----------------------
链式前向星
使用链式前向星的优劣： 优势：
1. 速度快，无需O2
2. 不受 C++版本限制，适用于所有题目
劣势：
1. 数组模拟链表，初学者不易理解
2. 码量多，不理解容易打错，不易 Debug
存图方式
struct line
{
int ver; // 指向的结点
int next; // 下一条边
// int edge; // 边的权值
}node[MAX * 2]; // 新建链式前向星
int head[MAX]; // 表头数组
遍历方式
for(int son = head[crd]; son; son = node[son].next)
// 下略……
添加方式
// 前向星添加边（使用函数）
// tot为所有边的数量，初始值为0
void add(int u, int v/*, int edge*/)
{
node[++tot].next = head[u];
node[tot].ver = v;
//node[tot].edge = edge;
head[u] = tot;
}
via サン猫の時間漂流
【动态规划】状态压缩DP
前言
二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？
这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个$[0, K^N - 1]$之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。
状态压缩的题目一般只有两种状态（当然也有三种状态的
集合操作
在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：$9 -> (1001)_{2}$ ，可以等效替换为一个 bool 数组$B[4] = {1, 0, 0, 1}$。下面是集合的常用操作：
| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:
● OI 学习笔记
● 动态规划 pubDate: 2023-06-10 00:00:00 tags:
● 优化
● 状态压缩
● DP
● 动态规划
● cpp
● OI title: 【动态规划】状态压缩 DP badge: old
----------------------
-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |
上机实践
售货员的难题
构思（朴素算法）
看一下题目……最短路是吧？但是要求经过所有结点。
所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为$O(N * N!)$，属于是必死无疑。
下面给出一段基础搜索代码，包含基础剪枝，得分$80Pt$.
via サン猫の時間漂流
前言
二进制的很多应用离不开集合这个概念，我们都知道在计算机当中，所有数据都是以二进制的形式存储的。一般一个 int 整形是 4 个字节，也就是 32 位 bit，我们通过这 32 位 bit 上 0 和 1 的组合可以表示多大 21 亿个不同的数。如果我们把这 32 位 bit 看成是一个集合，那么每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的。那么我们可不可以用一个数来保存一维的 DP 状态呢？
这当然是可行的，动态规划的过程是随着阶段的增长，在每一个状态维护上不断扩展的。而对于某些题目，我们扩展时需要记录一个状态集合，保存状态信息，以便进行状态转移。而状态压缩则是把这一个大小不超过 N、元素小于 K 的集合看做是一个 N 位的 K 进制数，以一个$[0, K^N - 1]$之间的十进制整数的形式作为 DP 状态的一维。这样我们就可以只用一个十进制整数，就保存了一个状态信息——这就是状态压缩。
状态压缩的题目一般只有两种状态（当然也有三种状态的
三进制题目）。这里只讨论最常见的二进制状态压缩，K 进制状态压缩可以以此类推，不再赘述。集合操作
在二进制状态 DP 中，我们用一个十进制整数代表一个集合，例如：$9 -> (1001)_{2}$ ，可以等效替换为一个 bool 数组$B[4] = {1, 0, 0, 1}$。下面是集合的常用操作：
| 操作含义 | 代码 | | :abbrlink: 122ed47c mathjax: true categories:
● OI 学习笔记
● 动态规划 pubDate: 2023-06-10 00:00:00 tags:
● 优化
● 状态压缩
● DP
● 动态规划
● cpp
● OI title: 【动态规划】状态压缩 DP badge: old
----------------------
-----------------------------------: | :----------------: | | 取出整数 n 在二进制表示下的第 k 位 | (n >> k) & 1 | | 取出整数 n 在二进制表示下的第 0k-1 位（后 k 位） | n & ((1 << k) - 1) | | 把整数 n 在二进制下表示的第 k 位取反 | n ^ (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 1 | n| (1 << k) | | 对整数 n 在二进制表示下的第 k 位赋值 0 | n & ( (1 << k)) | | 判断整数 n 在二进制表示下的第 k 位是否为真 | n & (1 << (k - 1)) |
注意了！我们常说的第一位在二进制表示下其实是第零位，程序实现时一定要注意当前真正在操作的是哪一位，否则 WA 了很难找出错误。
上机实践
售货员的难题
经典例题，状态压缩 DP 入门题：P1171 售货员的难题。
构思（朴素算法）
看一下题目……最短路是吧？但是要求经过所有结点。
所以优先队列 BFS 最短路这种就不管用啦！那么既然要走过所有村庄，直接枚举全排列输出，暴力省事。时间复杂度为$O(N * N!)$，属于是必死无疑。
下面给出一段基础搜索代码，包含基础剪枝，得分$80Pt$.
#include<cstdio>
using namespace std;
int lxy[21][21],hrb[21];
int n,i,j,k,minn=1e9;
int ss(int x,int y,int z)//x表示村子编号，y表示走了几个村子，z表示用的时间
{
if(z > minn) return 0;//基本最小值剪枝
if(y == n && z + lxy[x][1] < minn)
{
minn = z + lxy[x][1];
return 0;
}//比较求最小值，其中的加lxy[x][1]意思是走回第一个村
for(int i = 2; i <= n; i++)//循环开始
{
if(hrb[i]==0&&i!=x)//深搜模板，没走就搜
{
hrb[i] = 1;//打上标记
ss(i,y + 1, z + lxy[x][i]);
hrb[i] = 0;//回溯
}
}
return 0;
}
int main()
{
scanf("%d", &n);
for(i = 1;i <= n; i++)
for(k = 1;k <= n; k++)
scanf("%d", &lxy[i][k]);//输入
ss(1, 1, 0);//开搜
printf("%d",minn);
}
via サン猫の時間漂流
【动态规划】LIS与LCS（最长上升子序列）
引子-LIS 问题
这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下:
----------------------
LIS 的朴素解法
最朴素的想法就是用一个数组$DP[i]$表示在$1-i$范围内的 LIS 长度，初始化$DP[i]$为$1$（它自己一个数作为一个 LIS）。如果在小于$1-i$的范围内有满足 LIS 定义的情况，就可以转移$DP[i]$的值，代表选入这个范围和$A[i]$做为 LIS 的一部分。
我们要遍历到$DP[i]$时同时遍历所有在$1-i$内的状态，显然每次转移都是$O(N)$的时间复杂度，总复杂度为$O(N^2)$，状态转移方程如下：
$DP[i] = max(DP[i], DP[j] + 1) | (j < i)$
显然$O(N^2)$的时间复杂度是无法满足 OIer 的，因此我们要进行优化。
----------------------
LIS 的贪心二分优化
优化思路
为什么朴素算法慢呢？因为我们把所有情况枚举了一遍，而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间，自然就不行了。
我们知道，LIS 是一个严格单增的数列，那么在两个 LIS 长度相同的情况下，我们希望它能扩展到的长度尽可能长，自然是希望LIS 结尾元素尽可能小。那么思路就有了，我们使用一个数组$G[i]$保存长度为$i$的 LIS 的结尾元素值记录当前最长的 LIS 长度为$tot$，对于每一个$A[i]$，如果$A[i] > G[tot]$，说明当前可以把$A[i]$接到这一条所谓最长的 LIS 后面，则$G[++tot] = A[i]$。
那么我们的问题就是如何维护$G$数组。其实很简单，思路就是我们上面的思路，但是有一个问题，如果$A[i] \leq G[tot]$，应该怎么办呢？
那么根据我们的优化思路，我们要尽可能确保当前$G$数组里面存储的是当前长度为$i$的 LIS 序列的最优解，也就是
二分优化
显然，$G$数组是一个单调递增的数组，自然地可以使用二分查找优化时间复杂度。把时间复杂度降到$O(N,log,N)$级别。
代码整合
那么到目前为止，我们亲爱的$DP$数组就寿终正寝了，换成了我们新的$G$数组（
下面是代码示例，基础 LIS：
LIS 例题
这里给出一道 LIS 模板题：导弹拦截 LIS 经典。
将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。（其实只要判断改一下就好啦！）
第一问
没什么好说的，跑一次示例代码完事。
第二问
那么既然是单调不升子序列，我们考虑朴素算法，那么$G$数组就要求存储最大的值，每次执行完一次计算，就把选中的元素移除。重复计算，直到全部移除，记录计算次数，输出为答案。
但是这样显然太笨了！我们要优化优化优化！
我们不妨改变一下$G$数组的含义，用$G[i]$存第$i$个系统当前能够拦截的高度，同时我们把这些系统按从小到大排列——类似于原来的$G$数组。显然每次遍历到导弹$A[i]$时，我们拿最小的$G[i] \geq A[i]$是最优解。然后更新$G[i]$的值，显然更新之后排列还是从小到大，$G$数组仍然是单调递增的，因此不需要重新排序。当然如果没有满足$G[i] \geq A[i]$的情况，就新增一个系统。
只要我们仍然保存时间复杂度在$O(N,log,N)$ 级别，可以通过$10^5$的数据。
代码整合
下面是 AC 代码：
via サン猫の時間漂流
引子-LIS 问题
这几天在学习DP（动态规划），里面第一个接触到的问题就是LIS问题，这里简单概述如下:
给定一个长度为$N$的数列$A$，求数值单调递增的子序列的的长度最长是多少？其中 LIS（最长上升子序列）指的是从序列 A 中选择若干个 i，使得$i_{1}<i_{2}<i_{3}...<i_{n}$的同时满足$A_{i_{1}}<A_{i_{2}}<A_{i_{3}}...<A_{i_{n}}$。
----------------------
LIS 的朴素解法
最朴素的想法就是用一个数组$DP[i]$表示在$1-i$范围内的 LIS 长度，初始化$DP[i]$为$1$（它自己一个数作为一个 LIS）。如果在小于$1-i$的范围内有满足 LIS 定义的情况，就可以转移$DP[i]$的值，代表选入这个范围和$A[i]$做为 LIS 的一部分。
我们要遍历到$DP[i]$时同时遍历所有在$1-i$内的状态，显然每次转移都是$O(N)$的时间复杂度，总复杂度为$O(N^2)$，状态转移方程如下：
$DP[i] = max(DP[i], DP[j] + 1) | (j < i)$
显然$O(N^2)$的时间复杂度是无法满足 OIer 的，因此我们要进行优化。
----------------------
LIS 的贪心二分优化
优化思路
为什么朴素算法慢呢？因为我们把所有情况枚举了一遍，而最后留下的只有一种。LIS 的朴素算法在那些本不需要枚举的状态上浪费了时间，自然就不行了。
我们知道，LIS 是一个严格单增的数列，那么在两个 LIS 长度相同的情况下，我们希望它能扩展到的长度尽可能长，自然是希望LIS 结尾元素尽可能小。那么思路就有了，我们使用一个数组$G[i]$保存长度为$i$的 LIS 的结尾元素值记录当前最长的 LIS 长度为$tot$，对于每一个$A[i]$，如果$A[i] > G[tot]$，说明当前可以把$A[i]$接到这一条所谓最长的 LIS 后面，则$G[++tot] = A[i]$。
那么我们的问题就是如何维护$G$数组。其实很简单，思路就是我们上面的思路，但是有一个问题，如果$A[i] \leq G[tot]$，应该怎么办呢？
那么根据我们的优化思路，我们要尽可能确保当前$G$数组里面存储的是当前长度为$i$的 LIS 序列的最优解，也就是
结尾元素尽可能小的情况。所以我们要在$G$数组中找到第一个大于$A[i]$的元素$G[j]$，用$A[i]$更新$G[i]$。可是如果单纯遍历，复杂度又双叒叕回到了$O(N^2)$级别，所以……
二分优化
显然，$G$数组是一个单调递增的数组，自然地可以使用二分查找优化时间复杂度。把时间复杂度降到$O(N,log,N)$级别。
代码整合
那么到目前为止，我们亲爱的$DP$数组就寿终正寝了，换成了我们新的$G$数组（
什么NTR剧情）。下面是代码示例，基础 LIS：
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9
using namespace std;
int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;
int main()
{
int N = 0; //长度
for(int i = 1; i <= N; i++)
{
scanf("%d", &A[i]);
G[i] == INF; //初始化为1e9
}
G[1] = A[1]; //我们开始的起点
for(int i = 2; i <= N; i++)
{
if(A[i] > G[tot]) //只要能插入，就先插入
G[++tot] = A[i]; //初始化最后一个元素值
else
{
int l = 1, r = tot, mid; //新建变量
while (l < r)
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] > A[i]) r = mid;
else l = mid + 1;
}
G[l] = min(G[l], A[i]); //赋值，加MIN保险
}
}
printf("%d", tot); //输出答案
return 0;
}
LIS 例题
这里给出一道 LIS 模板题：导弹拦截 LIS 经典。
将拦截的导弹的高度提出来成为原高度序列的一个子序列，根据题意这个子序列中的元素是单调不增的（即后一项总是不大于前一项），我们称为单调不升子序列。本问所求能拦截到的最多的导弹，即求最长的单调不升子序列。（其实只要判断改一下就好啦！）
第一问
没什么好说的，跑一次示例代码完事。
注意这里$G$数组递减！请修改二分查找！
第二问
那么既然是单调不升子序列，我们考虑朴素算法，那么$G$数组就要求存储最大的值，每次执行完一次计算，就把选中的元素移除。重复计算，直到全部移除，记录计算次数，输出为答案。
但是这样显然太笨了！我们要优化优化优化！
我们不妨改变一下$G$数组的含义，用$G[i]$存第$i$个系统当前能够拦截的高度，同时我们把这些系统按从小到大排列——类似于原来的$G$数组。显然每次遍历到导弹$A[i]$时，我们拿最小的$G[i] \geq A[i]$是最优解。然后更新$G[i]$的值，显然更新之后排列还是从小到大，$G$数组仍然是单调递增的，因此不需要重新排序。当然如果没有满足$G[i] \geq A[i]$的情况，就新增一个系统。
只要我们仍然保存时间复杂度在$O(N,log,N)$ 级别，可以通过$10^5$的数据。
代码整合
下面是 AC 代码：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAX 100005
#define INF 1e9
using namespace std;
int A[MAX]; //存数字
int G[MAX]; //我们亲爱的G数组
int tot = 1;
int main()
{
int N = 0; //长度
while(~scanf("%d",&A[++N])); --N;
G[1] = A[1]; //我们开始的起点
for(int i = 2; i <= N; i++)
{
if(A[i] <= G[tot]) //只要能插入，就先插入
G[++tot] = A[i]; //初始化最后一个元素值
else
{
int l = 1, r = tot, mid;
while (l < r)//获得下标，注意这里G数组递减
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] >= A[i]) l = mid + 1;
else r = mid;
}
G[l] = max(G[l], A[i]); //赋值，加MAX保险
}
}
printf("%d\n", tot); //输出答案一
//重置数据
tot = 1;
memset(G, INF, sizeof(G));
G[1] = A[1];
for(int i = 2; i <= N; i++)
{
int l = 1, r = tot, mid;
while (l < r)//获得下标，当然也可能没有
{
//基础二分查找
mid = (l + r) >> 1;
if(G[mid] >= A[i]) r = mid;
else l = mid + 1;
}
if(G[l] >= A[i]) G[l] = A[i]; //如果找得到，赋值
else G[++tot] = A[i]; //如果找不到，初始化一个新的系统
}
printf("%d\n", tot); //输出答案二
return 0;
}
via サン猫の時間漂流
隐说 No.8 真正的危险在于仍用过去的逻辑做事
1、转型警惕路径依赖 “动荡时代最大的危险不是动荡本身，而是仍然用过去的逻辑做事” —— 彼得·德鲁克 太隐识：转型的根本在于转变底层逻辑，如果底层逻辑没有改变，仍然是过去的传统形式，那么又何谈改变呢。那么被历史和市场淘汰也是可以预料的事情了。 2、参禅 真正的参禅，也重在作务，重在生活。百丈禅师说：“搬柴运水，无非是禅；扬眉瞬目，无非是道。”因此，真正的禅是什么？搬柴运水是禅，腰石舂米是禅，犁田锄草是禅，早耕晚课是禅，忍耐慈悲是禅，劳苦牺牲是禅，方便灵巧是禅，棒喝教化是禅。......
READ MORE
via 太隐 (author: Ludwig Wang)
1、转型警惕路径依赖 “动荡时代最大的危险不是动荡本身，而是仍然用过去的逻辑做事” —— 彼得·德鲁克 太隐识：转型的根本在于转变底层逻辑，如果底层逻辑没有改变，仍然是过去的传统形式，那么又何谈改变呢。那么被历史和市场淘汰也是可以预料的事情了。 2、参禅 真正的参禅，也重在作务，重在生活。百丈禅师说：“搬柴运水，无非是禅；扬眉瞬目，无非是道。”因此，真正的禅是什么？搬柴运水是禅，腰石舂米是禅，犁田锄草是禅，早耕晚课是禅，忍耐慈悲是禅，劳苦牺牲是禅，方便灵巧是禅，棒喝教化是禅。......
READ MORE
via 太隐 (author: Ludwig Wang)
