36 KiB
动态规划
背包
01背包
给定 n 个物品，第 i 个的体积为 $v_i$，价值为 $w_i$，每个物品至多选一次，求最大价值。
转移方程 f(i, j) = max(f(i - 1, j), f(i - 1, j - v_i) + w_i)
时间复杂度 O(nm)
完全背包
给定 n 个物品，第 i 个的体积为 $v_i$，价值为 $w_i$，每个物品无限拿，求最大价值。
转移方程 f(i, j) = max(f(i - 1, j), f(i, j - v_i) + w_i)
时间复杂度 O(nm)
多重背包
给定 n 个物品，第 i 个的体积为 $v_i$，价值为 $w_i$，每个物品有 t_i 个，求最大价值。
考虑 t_i 的二进制，若第 k 位为 $1$，则新建一个体积为 $v_i 2^k$，价值为 w_i 2^k 的物品，转换为01背包。
时间复杂度 O(nm \log m)
混合背包
因为 dp 数组并没有规定是哪种背包，所以共用一个数组， 分三类做即可。时间复杂度 O(nm)
分组背包
有 n 个物品，第 i 个物品价值为 w_i 体积为 v_i 并且属于第 t_i 组。
有一个容量为 m 的背包，问在每组最多选一个且体积不超过 W 的条件下的最大价值。
一组一组进行考虑。对于每一组，从大到小枚举 j 表示这一组的体积，然后枚举每一个物品即可。
核心代码：
for (int i = 1; i <= m; ++i)
{
for (int j = W; j >= 0; --j)
{
for (auto x : items[i])
{
if (j >= v[x])
f[j] = max(f[j], f[j - v[x]] + w[x]);
}
}
}
有依赖的背包
金明有 n 元钱， m 个物品，第 i 件物品的价格为 $v_i$，重要度为 $p_i$。有些物品是主件，可以直接购买；有些物品是附件，要先买下主件才能买附件。
求最大的 v_i \times p_i
$n \le 3.2 \times 10^4, m \le 60, 0 \le v_i \le 10^4, 1 \le p_i \le 5$。每个主件最多有两个附件。
对于每个主件 A 以及附件 $B, C$，只有这几种选法： \varnothing, \{A\}, \{A, B\}, \{A, C\}, \{A, B, C\}
考虑将其转换为每组 4 个物品的分组背包求解。
背包问题的第 k 优解
普通01背包只能求出最优解，在普通背包上稍作改动，增加一维用于记录当前状态前 k 优解，即可求出背包问题的第 k 优解。
具体的，考虑原本的转移： f_{i, j} = max(f_{i - 1, j}, f_{i - 1, j - v_i} + w_i)
所有不选 i 的构成序列 [f_{i - 1, j, 1}, ...,f_{i - 1, j, k}]
所有选 i 的构成序列 [f_{i - 1, j - v_i, 1} + w_i, ...,f_{i - 1, j - v_i, k} + w_i]
合并后即得到 f_{i, j, k}
时间复杂度 O(nmk)
背包例题
P4141 消失之物
有 n 个物品。体积分别是 $w_1, w_2, \dots, w_n$，每个只有一个。
记 cnt(i, x) 表示在丢掉第 i 件物品的情况下装满容量为 x 的背包的方案数。
输出一个 n \times m 的矩阵，表示每一个 cnt(i, x) 的个位数。（ m 为输入的背包容量最大值）
P4141题解
先按照不丢东西的方法跑一次背包。
然后考虑丢掉一件物品后造成的影响。
因为本题目要求的是方案数而不是最优值，所以每一个物品的贡献都可以撤销。
考虑转移方程
f_j = g_j + g_{j - w_i}\\
\Downarrow\\
g_j = f_j - g_{j - w_i}
因为需要用到更小的 $g_{j - w_i}$，所以从小到大循环即可逆推出 $g_i$。
P4141代码
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, w[N], f[N], g[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
#endif
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
f[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = m; j >= w[i]; --j)
f[j] = (f[j] + f[j - w[i]]) % 10;
for (int i = 1; i <= n; ++i)
{
memset(g, 0, sizeof(g));
g[0] = 1;
for (int j = 1; j <= m; ++j)
{
if (j - w[i] >= 0)
g[j] = (f[j] - g[j - w[i]] + 10) % 10;
else
g[j] = f[j] % 10;
printf("%d", g[j] % 10);
}
puts("");
}
return 0;
}
区间
区间dp是一种特殊的dp方式，他以每个子区间为一个状态，一般以 f_{l, r} 表示 [l, r] 的状态。
区间 dp 例题
P1775 石子合并
在一条路上有 n 个棋子，第 i 堆有 a_i 枚，每次操作可以合并相邻的两堆棋子，能获得的得分为两堆棋子的总和。问最大总得分。
n \le 300
P1775题解
设 f_{l, r} 表示 [l, r] 这个区间的答案。
转移方程式则为
f_{l, r} = \mathop{max}\limits_{i \le k \lt j}\{f_{i, k} + f_{k + 1, j}+\sum^{j}_{t = i} a_t\}
这题代码就不放了，重点是下面的变式。
P1175变式（P1880）
若石子摆成一个环而非一条链，如何解决？
P1880法1
做 n 次，时间复杂度 O(n^4)
P1880法2
将序列循环一次拼接到后边，再去执行原来的 dp，最后答案则为
max\{f_{1, n}, f_{2, n + 1}, \dots, f_{n, 2\times n - 1}\}
复杂度 O(n^3)
P1880代码
#include <bits/stdc++.h>
int n;
int a[500];
int f[500][500] = {0};
int fm[500][500] = {0};
int pre[500] = {0};
int ans_max = -1;
int ans_min = 0x7f7f7f7f;
int max(int a, int b)
{
if (a > b)
return a;
return b;
}
int min(int a, int b)
{
if (a < b)
return a;
return b;
}
int sum(int i, int j)
{
return pre[j] - pre[i - 1];
}
int main()
{
int i, j, k;
scanf("%d", &n);
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[n + i] = a[i];
}
int len = (n << 1) - 1;
for (i = 1; i <= len; i++)
{
pre[i] = pre[i - 1] + a[i];
}
memset(fm, 0x7f, sizeof(fm));
for (i = 0; i <= 400; i++)
fm[i][i] = 0;
for (i = 2; i <= n; i++)
{
for (j = 1; j <= len - i + 1; j++)
{
for (k = j; k < j + i - 1; k++)
{
int m = f[j][k] + f[k + 1][j + i - 1];
int xiao = fm[j][k] + fm[k + 1][j + i - 1];
if (f[j][j + i - 1] < m)
f[j][j + i - 1] = m;
if (fm[j][j + i - 1] > xiao)
fm[j][j + i - 1] = xiao;
}
f[j][j + i - 1] += sum(j, j + i - 1);
fm[j][j + i - 1] += sum(j, j + i - 1);
}
}
for (i = 1; i <= n; i++)
{
if (ans_max < f[i][i + n - 1])
ans_max = f[i][i + n - 1];
if (ans_min > fm[i][i + n - 1])
ans_min = fm[i][i + n - 1];
}
printf("%d\n", ans_min);
printf("%d", ans_max);
return 0;
}
P10236 D. 排卡
给定一个长度为 n 的双端队列 $q$，进行 n 次操作，第 i 次操作令 b_i \leftarrow q 的队头或队尾，并弹出那个元素。
要求构造操作方式，使得
\sum^{n - 1}_{i = 1}pow(b_i, b_{i + 1}, 998244353)
最大。
其中 pow(a, b, p) = a^b \bmod p
注意：只对于每次计算取模，后续加起来时不取模。
n \le 10^3
P10236题解
考虑使用区间 dp，使用 f_{l, r, b} 表示 b = 0 时，访问的数是左边， b = 1 则表示右边， [l, r] 区间内的答案。则转移方程为：
f_{i + 1, j, 0} = max(f_{i + 1, j, 0}, f_{i, j, 0} + a^{a_i}_{i - 1}, f(i, j, 1) + a^{a_i}_{j + 1}) \\
f_{i, j - 1, 1} = max(f_{i, j - 1, 1}, f_{i, j, 1} + a^{a_i}_{j + `}, f(i, j, 0) + a^{a_i}_{i - 1}) \\
时间复杂度为 O(n^2)
P10236代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t, n, a[1005], f[1005][1005][2], mod = 998244353;
int fast_pow(int a, int b, int c = mod)
{
if (a == 0 && b == 0)
return 0;
int x, y, m = 1;
y = a, x = b;
while (b)
{
if (b % 2)
m = m * a % c;
a = a * a % c;
b /= 2;
}
return m;
}
signed main()
{
scanf("%lld", &t);
while (t--)
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
memset(f, 0, sizeof(f));
//-----------------dp-------------------//
for (int len = 1; len < n; len++)
for (int i = 1; i + len <= n; i++)
{
f[i][i + len][0] = max(f[i + 1][i + len][0] + fast_pow(a[i], a[i + 1]), f[i + 1][i + len][1] + fast_pow(a[i], a[i + len])); // left
f[i][i + len][1] = max(f[i][i + len - 1][0] + fast_pow(a[i + len], a[i]), f[i][i + len - 1][1] + fast_pow(a[i + len], a[i + len - 1])); // right
}
printf("%lld\n", max(f[1][n][0], f[1][n][1]));
}
return 0;
}
P1450 硬币购物
共有 4 种硬币。面值分别为 $c_1, c_2, c_3, c_4$。
某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。
1 \le n \le 1000
P1450题解
若直接套用多重背包，肯定爆时间。
P1450代码
#include <bits/stdc++.h>
using namespace std;
unsigned long long c[5];
int n;
unsigned long long d[5];
unsigned int t;
int main()
{
#ifndef ONLINE_JUDGE
freopen("3.in", "r", stdin);
#endif
scanf("%llu%llu%llu%llu%d", &c[0], &c[1], &c[2], &c[3], &n);
while (n--)
{
scanf("%llu%llu%llu%llu%u", &d[0], &d[1], &d[2], &d[3], &t);
vector<unsigned long long> f(t + 1);
f[0] = 1;
for (size_t o = 0; o < 4; ++o)
{
unsigned int w = c[o], m = d[o];
vector<unsigned long long> g(f);
vector<unsigned long long> s(w);
for (unsigned long long i = 0; i * w <= t; ++i)
for (unsigned long long j = 0; j < w && i * w + j <= t; ++j)
{
g[i * w + j] += s[j];
s[j] += f[i * w + j];
if (i >= m)
s[j] -= f[(i - m) * w + j];
}
f = g;
}
printf("%llu\n", f.back());
}
return 0;
}
P5365 英雄联盟
有 n 个英雄，每个英雄有 k_i 个皮肤i，一个英雄所有的皮肤价格相同，都是 $c_i$，现在要买皮肤来进行展示，展示的方案就是每个英雄选择一个皮肤展示，求如何花最少的前使得总的展示方案 $\le m$。
n \le 130, m \le 10^{17}, k_i \le 10, c_i \le 200
P5365题解
朴素方案是 f_{i, j} 表示前 i 个物品，方案数至少为 j 的最小花费，但是观察到 $m \le 10^17$，方案数过多，肯定存不下。
于是考虑使用 f_{i, j} 表示前 i 个物品，价格最大为 j 的最大方案数，就转换为了一个多重背包，转移为：
f_{i + 1, j + c_i \times t} = max \{f(i, j)\times t\}
其中 t 表示买了 t 个皮肤。
时间复杂度 O(n^2kc)
- 注意：为了防止溢出，方案数要与
m取 min
P5365代码
#include <bits/stdc++.h>
// fi = max(fi, f[i - g * c[p]] * g)
#define int long long
const int N = 1000005;
using namespace std;
int f[N], k[N], c[N], n, m, sq, ans;
signed main()
{
f[0] = 1;
#ifndef ONLINE_JUDGE
freopen("4.in", "r", stdin);
#endif
scanf("%lld%lld", &n, &m);
for (int p = 1; p <= n; ++p)
scanf("%lld", &k[p]);
for (int p = 1; p <= n; ++p)
{
scanf("%d", &c[p]);
sq += k[p] * c[p];
}
for (int p = 1; p <= n; ++p)
for (int i = sq; i >= 0; --i)
for (int g = 0; g <= k[p] && g * c[p] <= i; ++g)
f[i] = max(f[i], f[i - g * c[p]] * g);
while (ans < sq && f[ans] < m)
++ans;
printf("%d\n", ans);
}
LOJ3254 集邮比赛 3
JOI 君生活的 IOI 国有一个著名的湖泊，今天一场集邮大会在湖边举行。
绕湖一圈总共有 N 种邮票可以收集，编号分别为 $1\ldots N$，收集点绕湖顺时针排列。湖的周长为 $L$，第 i 张邮票 (1 \le i \le N) 的收集点在距离出发点顺时针走 X_i 米的位置。
参赛者在比赛开始的时候要站在出发点的位置，当大会开始时，参赛者可以绕湖顺时针或者逆时针移动，参赛者能够得到第 i 张邮票 (1 \le i \le N) 当且仅当他到达收集点的时间在比赛开始时的 T_i 秒以内（含）。
JOI 君也是集邮大会的参与者。他的移动速度是每秒钟 1 米，你可以认为只有移动才会消耗时间。
计算他最多能收集到多少种邮票。
n \le 200, 2 \le L \le 10^9, 0 \le T_i \le 10^9
LOJ3254题解
LOJ3254代码
树形
树形 dp 本质上只是一种思想，就是把 dp 建立在树形结构上。树形 dp 最主要的特征就是考虑树上的父子关系，例如选择一个节点必须选择或不能选择父亲等。
常见的树形 dp 有两种模型：
- 选择节点类，转移方程类似 $f_{i, 0} = f_{j, 1}, f_{i, 1} = max(f_{j, 0}, f_{j, 1})$，主要是处理树上某个节点是否选择。
- 树形背包类，转移方程类似 $f_{v, k} = f_{u, k} + val, f_{u, k} = max(f_{v, k}, f_{v, k - 1})$，主要是处理树上背包问题。
选择节点类树形 dp
这一类的 dp 主要是处理某一个节点是否对答案产生贡献，即是要选择该答案到答案集合中取。所以在设计转移方程 f_{i, 0/1} 时，第二维则表示该节点是否选取。
树形背包类树形 dp
该类 dp，通常是在树上选择一个包含根的连通块，或者背包存在依赖关系，或者需要知道每个点的子树选了多少。
树形 dp 例题
树上最小点覆盖
给定一个 n 个节点的树，要求选择一个点的集合，使得树上每一条边都与其中至少一个点相连，同时让集合大小最小。
n \le 10^6
树上最小点覆盖题解
使用状态 f_{i, 0/1} 表示节点 i 选择或不选择。
考虑 DFS 进行状态转移，对于节点 $u$，以及其子节点集合 $V_s$，有如下转移：
\begin{aligned}
f_{u, 1} &= \sum_{v \in V_s} min(f_{v, 0}, f_{v, 1}) \\
f_{u, 0} &= \sum_{v \in V_s} f_{v, 1} \\
\end{aligned}
P2014 选课
有 n 个学科，每门课有个学分，每门课程有一门或者没有先修课（若课程 a 是课程 b 的先修课，则必须先修课程 a 在能学习课程 $b$）。一个学生要从这些课程内选择 m 门课程进行学习，问他能获得的最大学分。
1 \le n, m \le 300
P2014题解
考虑构造树形关系，在 dfs 时转移。记 f_{u, i, j} 表示 u 为根的子树中，已经遍历了 i 课子树，选择了 j 门课的最大学分。转移方程如下：
f_{u, i, j} = \mathop{max}_{k \le min(j, sz_v)}(f_{u, i - 1, j - k} + f_{v, s_v, k})
其中 s_v 表示 v 的子节点数量， sz_v 表示以 v 为根的树的节点数量。
P1352 没有上司的舞会
某个大学有 n 个职员，编号为 $1 \dots n$，他们之间有从属关系，也就是说他们的关系构成一棵树，父节点则为他们的直接上司。
现在有一个舞会，每个职员去了之后会增加 r_i 的快乐指数，但是若一个职员的直接上司去了，那这个职员就不肯去了。
求最大快乐指数。
1 \le n \le 6000, -128 \le r_i \le 127
P1352题解
记录 f_{u, 0/1} 表示以 u 为根的子树，且 u 选或不选的最大快乐指数， V_u 为节点 u 的孩子节点集合。转移方程为：
\begin{aligned}
f_{u, 0} &= \sum_{v \in V_u} max(f_{v, 1}, f_{v, 0}) \\
f_{u, 1} &= r_u + \sum_{v \in V_u} f_{v, 0} \\
\end{aligned}
时间复杂度 O(n)
P1352代码
#include <stdio.h>
#include <vector>
using namespace std;
int n, fa[6005], f[6005][2], r[6005];
vector<int> child[6005];
void dp(int m)
{
for (int i = 0; i < child[m].size(); ++i)
{
dp(child[m][i]);
}
f[m][1] = r[m];
for (int i = 0; i < child[m].size(); ++i)
{
f[m][0] += max(f[child[m][i]][0], f[child[m][i]][1]);
f[m][1] += f[child[m][i]][0];
}
return;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &r[i]);
}
for (int i = 1; i < n; ++i)
{
int l, k;
scanf("%d%d", &l, &k);
fa[l] = k;
child[k].push_back(l);
}
int root = 1;
while (fa[root] != 0)
{
root = fa[root];
}
dp(root);
printf("%d\n", max(f[root][0], f[root][1]));
return 0;
}
P2899 Cell Phone Network G
有一个有 n 个节点的树形地图，一个节点如果建立电话干，那么和他直接相连的顶点也会被覆盖到。问最少建多少个电话杆，可以使所有顶点被覆盖。
1 \le n \le 10^4
P2899题解
该题目的重点在于，一个点的选取不仅会影响孩子节点，还会影响父亲节点，所以转移会复杂一些。
- 记
f_{i, 0}表示选 $i$，且以i为根的子树每个点都被覆盖的最少信号塔部署数量。 - 记
f_{i, 1}表示不选 $i$，且i被儿子覆盖的最少信号塔数量。 - 记
f_{i, 2}表示不选 $i$，且以i为根的子树每个点都被覆盖的最少信号塔部署数量，即i要被父节点覆盖。
记 V_i 为 i 的子节点点集。
转移方程：
f_{i, 0} = 1 + \sum_{v \in V_i} min(f_{v, 0}, f_{v, 1}, f_{v, 2}) \\
f_{i, 2} = \sum_{v \in V_i} min(f_{v, 0}, f_{v, 1}) \\
如果存在 $k \in V_i \And f_{k, 0} \le f_{k, 1}$，则
f_{i, 1}= \sum_{v \in V_i} min(f_{v, 1}, f_{v, 0})
否则
t \leftarrow \{min(f_{v, 0} - f_{v, 1}), v \in V_i\}\\
f_{i, 1}= \sum_{v \in V_i} min(f_{v, 1}, f_{v, 0}) + t
P2899代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, INF = 0x7f7f7f7f;
int n, m, dp[N][5];
int nxt[N], to[N];
int head[N], cnt;
void add(int too, int from)
{
to[++cnt] = too;
nxt[cnt] = head[from];
head[from] = cnt;
}
void dfs(int u, int fa)
{
int tot = 0, g[N];
dp[u][0] = 1;
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (v == fa)
continue;
dfs(v, u);
dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
dp[u][1] += dp[v][0];
dp[u][2] += min(dp[v][0], dp[v][1]);
g[++tot] = dp[v][1] - dp[v][0];
}
if (!tot)
dp[u][1] = INF;
else
{
sort(g + 1, g + 1 + tot);
for (int i = 1; i < tot; i++)
{
if (g[i] < 0)
dp[u][1] += g[i];
else
break;
}
}
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("5.in", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
dfs(1, 0);
printf("%d", min(dp[1][0], dp[1][1]));
return 0;
}
换根
换根 dp，又称作二次扫描，相比与普通的树形 dp，换根 dp 的特点是不具有固定的根节点。而最终要求的是哪个节点为根时答案最优。
换根 dp 解决的问题，便是在节点数为 n 的树中，朴素做法则为进行 n 次树形 dp，而换根 dp 则是求出换根所带来的影响，以降低 n 倍的复杂度。
换根后，大部分的情况不变，变得只是旧根和新根的子节点的父子关系，所以只需要处理这些关系后，即可单次树形 dp 求出所有点为根的答案。
主要步骤：
- 定根求解
- 计算换根
换根 dp 例题
P3478 STA-Station
给定一个 n 个点的树，求出一个节点，使得这个节点为根时，所有节点的深度之和最大。
1 \le n \le 10^6
P3478题解
若直接进行 n 次树形 dp，时间肯定会爆。
考虑固定 1 号节点为根，则可以直接求出以 u 为根的子树内所有节点的深度和 $f_u$。
接下来考虑换根，使用 f_u 表示以 u 为根节点时所有节点的深度和。
记 u 为 v 的父亲， sz_u 表示以 u 为根的子树大小（以 1 为根时），则转移方程为
f_v = f_u - sz_v + (sz_1 - sz_v)
这个转移方程的含义是：
- 第一个
-sz_v表示根节点为v时，原来根节点为v的子树的所有深度都-1 - 第二个
+(sz_1 - sz_v)表示根节点为v时，原来根节点为u且不在v子树内的节点深度都+1
这样就可以快速求出换根后对答案产生的贡献。
P3478代码
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int n;
int to[N], nxt[N];
int dep[N], head[N], tot;
void add(int a, int b)
{
to[++tot] = b, nxt[tot] = head[a], head[a] = tot;
}
int siz[N];
long long dp[N];
void search(int u, int fa)
{
siz[u] = 1, dp[u] = dep[u];
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (v == fa)
continue;
dep[v] = dep[u] + 1;
search(v, u);
siz[u] += siz[v], dp[u] += dp[v];
}
}
void chroot(int u, int fa)
{
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i];
if (v == fa)
continue;
dp[v] = dp[u] - siz[v] + n - siz[v];
chroot(v, u);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("3.in", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
search(1, 0);
chroot(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++)
ans = (dp[ans] < dp[i]) ? i : ans;
printf("%d\n", ans);
}
CF543D Road Improvement
一个国家有 n 座城市和 n - 1 条双向道路，你可以沿道路从一个城市到任意一个其他城市。这些城市被编号 1 \dots n
所有最初的城市都是不良的，但是政府想要改善道路情况。我们认为从首都 x 到其他城市的道路上的不良道路数量 $\le 1$，则市民会感到满意。求对于每个可能的 $x$，求出所有能满足市民条件的改善道路方案的数量 \bmod 10^9 + 7
2 \le n \le 2 \times 10^5
CF534D题解
考虑定根的情况，记 f_i 表示以 i 为根的子树改良方案数量，那么对于所有叶子节点， f_i = 1
对于非叶子节点 $u$，记 $v \in V_u$，若 u, v 之间没有改良，那么 v 子树内所有道路都要改良，方案数为 $1$。如果这条道路改良了，那么方案数为 $f_v$。转移为
f_u = \prod_{v \in V_u} (f_v + 1)
接下来考虑换根。
发现在将根从 u 变为他的儿子 v 的时候，只有 f_u, f_v 发生变化。
设 f'_u 为换根后 f_u 的新值。则
f'_u = \prod_{k \in V_u, k \not= v}(f_k + 1) \\
f'_v = f_v(f_u + 1) \\
即可换根求解。
CF534D代码
#include <bits/stdc++.h>
const int mod = 1e9 + 7, M = 5e5 + 10;
using namespace std;
int n, nxt[M], head[M], to[M], tot;
long long F[M], ans[M];
vector<long long> F1[M], F2[M];
int read()
{
char c = getchar();
int ans = 0;
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
ans = (ans << 1) + (ans << 3) + (c ^ 48), c = getchar();
return ans;
}
void add(int u, int v)
{
nxt[++tot] = head[u], head[u] = tot, to[tot] = v, nxt[++tot] = head[v], head[v] = tot, to[tot] = u;
}
void dfs1(int x, int fa)
{
F[x] = 1;
for (int i = head[x]; i; i = nxt[i])
if (to[i] != fa)
dfs1(to[i], x), F[x] = F[x] * (F[to[i]] + 1) % mod;
}
void dfs2(int x, int fa)
{
ans[x] = 1;
for (int i = head[x]; i; i = nxt[i])
{
ans[x] = ans[x] * (F[to[i]] + 1) % mod;
if (to[i] != fa)
F1[x].push_back(F[to[i]] + 1), F2[x].push_back(F[to[i]] + 1);
}
for (int i = 1; i < F1[x].size(); i++)
F1[x][i] = F1[x][i] * F1[x][i - 1] % mod;
for (int i = F2[x].size() - 2; i >= 0; i--)
F2[x][i] = F2[x][i] * F2[x][i + 1] % mod;
int cnt = 0;
for (int i = head[x]; i; i = nxt[i])
{
if (to[i] == fa)
continue;
F[x] = (fa ? F[fa] + 1 : 1);
if (cnt > 0)
F[x] = F[x] * F1[x][cnt - 1] % mod;
if (cnt < F2[x].size() - 1)
F[x] = F[x] * F2[x][cnt + 1] % mod;
dfs2(to[i], x);
++cnt;
}
}
int main()
{
n = read();
for (int i = 2; i <= n; i++)
add(read(), i);
dfs1(1, 0);
dfs2(1, 0);
for (int i = 1; i <= n; i++)
printf("%lld ", ans[i]);
return 0;
}
状压
状态压缩 dp，表示将一个集合压缩到一个二进制数来表示状态，常用于关于图中选择节点等的问题，这种问题的节点个数通常很少，一般 $\le 20$。并且，这种问题的转移通常与选择的节点顺序无关，只和最后一个选择的节点有关。
我们常用 f_{S, u} 表示经过了 S 中的节点，且最后一个经过的节点为 u 的结果。
当然，状压 dp 也可以用在线性结构上，一维 i 表示扫描进度，一维 S 进行状态压缩。（例题）
引入例题 旅行商问题
给定一个 n 个顶点组成的带权有向图的距离矩阵 $d(i, j)$。要求从顶点 0 出发，经过每个节点恰好一次后再回到节点 0
问经过的边权之和最短是多少。
n \le 15
旅行商问题题解
所有的路线有 (n - 1)! 种。
因为已经经过的点，除了最后一个，其他点的顺序对于后续没有影响，所以考虑使用 f_{S, v} 表示已经经过了 S 中的点，上一个经过的点是 v 的情况下经过的边权之和最短的值。
但是因为数组下标不能为数组，所以用一个 2^{15} 的 int 来表示状态，这便是状态压缩。即
mask(S) = \sum_{i \in S} 2^i
转移：
f_{\varnothing, 0} = 0 \\
f_{S, v} + d(u, v) \rightarrow f_{S \cup u, u}, u \notin S
常见技巧
位运算操作
1 << i // 只包含 i 的集合
(1 << n) - 1 // 1...n - 1 全集
if (S >> i & 1) // 判断 i in S
S | (1 << i) // S and i
S & ~(1 << i) // S without i
S | T // 并
S & T // 交
注意优先级：左右移 > 按位或，按位与 > 按位取反
popcount
popcount 定义：一个数的二进制中 1 的个数。
常见求法：
- 内置函数
__builtin_popcount(), __builtin_popcountll() - 预处理
int n;
int c[1 << 20] = {0};
int main()
{
for (int S = 1; S <= (1 << n); ++S)
c[S] = c[S ^ (S & (-S))] + 1;
}
int query(long long x)
{
return c[x & ((1 << 20) - 1)] + c[x >> 20];
}
状压 dp 例题
P2831 愤怒的小鸟
平面上有若干只猪 $(x_i, y_i)$，小鸟的飞行轨迹为 $ax^2 + bx$。当一只猪在小鸟的飞行轨迹上，这只猪将会被消灭，且不会影响小鸟的飞行。求最受需要多少只鸟才能把所有猪消灭。
P2831题解
考虑用 f_S 表示覆盖 S 这个集合所需要的最小数量， g_{i, j} 表示经过 i, j 两个点的抛物线所经过的集合。
f_{S|g_{i, j}} = min(f_{S|g_{i, j}}, f_S + 1)
P2831代码
P1896 互不侵犯
在 N \times N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。
$1 \le N \le 9$，0 \le K \le N \times N
P1896题解
使用 f_{i, j, l} 表示只考虑前 i 行，第 i 行按照编号 j 的状态放置国王，且已经放置 l 个国王。
因此，我们用二进制数 sit_j 表示国王的放置情况，使用 sta_j 表示该状态下的国王个数。因此，只需要在程序开始时枚举出行内的每种情况，转移的时候保证和上一行的情况不冲突即可。转移方程：
f_{i, j, l} = \sum f_{i - 1, x, l - sta(j)} \\
(sit_x << 1) \And sit(j)==0 \\
(sit_x >> 1) \And sit(j)==0 \\
P1896代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, K, cnt, a[1024], b[1024], f[20][1024][90];
void dfs(int k, int mask, int count)
{
if (k > N)
{
++cnt;
a[cnt] = mask;
b[cnt] = count;
return;
}
dfs(k + 1, mask * 2, count);
if ((mask & 1) == 0 && count < K)
dfs(k + 1, mask * 2 + 1, count + 1);
}
signed main()
{
scanf("%lld%lld", &N, &K);
dfs(1, 0, 0);
f[0][1][0] = 1;
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= cnt; ++j)
{
for (int k = b[j]; k <= K; ++k)
{
for (int last = 1; last <= cnt; ++last)
{
if (a[last] & a[j])
continue;
if ((a[last] << 1) & a[j])
continue;
if ((a[last] >> 1) & a[j])
continue;
f[i][j][k] += f[i - 1][last][k - b[j]];
}
}
}
}
int ans = f[N][1][K];
for (int j = 2; j <= cnt; ++j)
{
ans += f[N][j][K];
}
printf("%lld\n", ans);
return 0;
}
P4460 解锁屏幕
求平面上给定坐标的 n 个点中选出一条点数不小于 $4$，且经过的路径上的点必须被选中，可以重复经过已经经过的点但是每个点只能被选中一次的路径数量。
1 \le n \le 20
P4460题解
考虑 f_{S, i} 表示经过了 $S$，最后一个节点为 i 的方案数。
转移时选择一个 j 满足 j \in S \And \forall k \in \{S - j\}, P_k \notin P_iP_j
其中 P_k \notin P_iP_j 表示 k 不在 i, j 的路径中。
这样的时间复杂度为 $O(2_nn^3)$，无法通过，需要至少降掉一个 n 才可以通过。
于是考虑预处理 g_{i, j} 表示 P_i, P_j 经过的所有点的集合，枚举每一个点进行转移。
这样，复杂度就降为了 $O(n^22^n)$，可以通过。
P4460代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000007;
pair<int, int> p[25];
int dp[2500005][25], ans;
int f[25][25]; // 过i，j必须经过的点
bool cmp(pair<int, int> a, pair<int, int> b)
{
return a.first < b.first || (a.first == b.first && a.second < b.second);
}
long double work(int x1, int y1, int x2, int y2)
{
if (x1 == x2)
return INT_MAX;
return 1.0 * (y1 - y2) / (x1 - x2);
}
int n;
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
#endif
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i].first, &p[i].second);
// pre begin
sort(p + 1, p + n + 1, cmp);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
for (int k = i + 1; k <= j - 1; k++)
if (abs(work(p[i].first, p[i].second, p[k].first, p[k].second) - work(p[k].first, p[k].second, p[j].first, p[j].second)) <= 1e-7)
f[i][j] |= (1 << k), f[j][i] |= (1 << k);
// pre end
for (int i = 1; i <= n; i++)
dp[1 << i][i] = 1;
for (int i = 0; i < (1 << (n + 1)); i++)
for (int j = 1; j <= n; j++)
if (i & (1 << j))
for (int k = 1; k <= n; k++)
if ((i & (1 << k)) == 0 && k != j && (i & f[j][k]) == f[j][k])
dp[i | (1 << k)][k] = (dp[i | (1 << k)][k] + dp[i][j]) % MOD;
for (int i = 0; i < (1 << (n + 1)); i++)
if (__builtin_popcount(i) >= 4)
for (int j = 1; j <= n; j++)
if (i & (1 << j))
ans = (ans + dp[i][j]) % MOD;
printf("%d\n", ans);
return 0;
}
P6239 奇怪的道路
求有 n 个点， m 条边，每个点的度数都是偶数，且每条边连接的节点编号相差不超过 k 的无向图的数量 $\bmod 10^9 + 7$。
1 \le n, m \le 30, 1 \le k \le 8
P6239题解
使用 f(i, j, S) 表示考虑了前 i 个点，一共连接了 j 条边， [i - k, i - 1] 内的点目前度数奇偶性为 S 的方案数。考虑每次转移加入一个点。