---
tags: Programming Contest
---
# Educational DP Contest 題解（N ~ V）
## 心得
後半 13 題，比前半 13 題難上不少，讓我慢慢寫。
## N. [Slimes](https://atcoder.jp/contests/dp/tasks/dp_n)
給定長度為 $N$ 的序列 $A$，不斷重覆：「合併 $A$ 中的相鄰兩項 $x, y$ 為 $x + y$，花費成本 $x + y$」，直到 $A$ 只剩一個元素。請問在所有合併方法中，總成本最小能是多少？
設 $f(i, j)$ 為合併 $A$ 的半開區間 $[i, j)$ 為一個元素所需的最小成本。
如同 CLRS 中矩陣乘法的最小成本，我們採用 Divide & Conquer 的技巧。
我們枚舉分割點 $k$ 將 $[i, j)$ 拆成 $[i, k), [k, j)$，此時所需成本有三項：
1. 合併左區間為一個元素的成本 $f(i, k)$
2. 合併右區間為一個元素的成本 $f(k, j)$
3. 合併「左區間合併後的元素」 與「右區間合併後的元素」的成本
設 $S_{[a, b)}$ 為 $A_a + A_{a + 1} + \cdots + A_{b - 1}$，轉移方程可以寫成：
$$
f(i, j) = \min_{i \lt k \lt j} \left( f(i, k) + f(k, j) + (S_{[i, k)} + S_{[k, j)}) \right)
$$
$S_{[a, b)}$ 可以透過前綴和預處理，在轉移時就能 $O(1)$ 算出。實作採用 top-down dp。
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1e18;
int N;
ll A[400];
ll P[400];
ll dp[400][400 + 1];
ll sum(int i, int j) { return P[j - 1] - ((i >= 1) ? P[i - 1] : 0); }
ll f(int i, int j) { // [i, j)
if (dp[i][j] != INF) {
return dp[i][j];
}
if (j - i == 1) {
return 0;
}
ll ret = INF;
for (int k = i + 1; k < j; k++) {
ll val = f(i, k) + f(k, j) + sum(i, k) + sum(k, j);
ret = min(ret, val);
}
dp[i][j] = ret;
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
P[0] = A[0];
for (int i = 1; i < N; i++) {
P[i] = P[i - 1] + A[i];
}
for (int i = 0; i < N; i++) {
for (int j = i; j <= N; j++) {
dp[i][j] = INF;
}
}
cout << f(0, N) << endl;
return 0;
}
```
## O. [Matching](https://atcoder.jp/contests/dp/tasks/dp_o)
給定 NxN 的矩陣 $A_{i, j}$ 代表 man $i$ 能否與 woman $j$ 匹配，限定一個人最多只能有一個匹配，問有多少種匹配方式？
設 $dp[i, S]$ 為 $[0, i$) men 與 $S$ women 的匹配方法數，其中 $S$ 是集合。題目所求即為 $dp[N, \{0, 1, ..., N\}]$。
在狀態 $dp[i, S]$ 時，枚舉 men $i$ 能與哪些 woman 配對，假設是 $(i, j)$，我們得到：
$$
dp[i, S] \to dp[i + 1, S \cup \{j\}]
$$
當然此 $j$ 必需不在 $S$ 中。
```python
N = int(input())
M = 10 ** 9 + 7
A = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (1 << N) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
for s in range(1 << N):
if dp[i][s] != 0: # improve speed
for j in range(N):
if (s & (1 << j)) == 0 and A[i][j]:
dp[i + 1][s | (1 << j)] += dp[i][s]
dp[i + 1][s | (1 << j)] %= M
print(dp[N][(1 << N) - 1])
```
## P. [Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p)
給定一棵大小為 $N$ 的 tree，可以將每個節點染成白色或黑色，但要求不可以有相鄰的兩個節點都為黑色，問染色方法數？
設 $f(u, c)$ 為以 $u$ 為 root 的子樹的染色方法數，且 $u$ 是染成 $c$ (白色 = 1，黑色 = 0)。
若 u 為黑色，則其 children 必需染成白色；若 u 為白色，則其 children 是什麼顏色都可以。根據這個想法，我們得到轉移：
$$
\begin{align}
f(u, 0) &= \prod_{v \in child(u)} f(v, 1) \\
f(u, 1) &= \prod_{v \in child(u)} (f(v, 0) + f(v, 1))
\end{align}
$$
計算順序為葉子先算，再慢慢往上，直到算到 root。或我們可以用 top-down 實現。
```cpp
#include <atcoder/modint>
#include <iostream>
#include <vector>
using namespace std;
using mint = atcoder::modint1000000007;
const int MAX_N = 1e5;
int N;
mint dp[MAX_N][2];
vector<int> adj[MAX_N];
mint f(int u, int c, int p) {
if (dp[u][c] != 0) {
return dp[u][c];
}
mint res = 1;
for (auto v : adj[u]) {
if (v != p) {
if (c == 0) {
res *= f(v, 1, u);
} else {
res *= f(v, 0, u) + f(v, 1, u);
}
}
}
dp[u][c] = res;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int u = 0; u < N; u++) {
dp[u][0] = dp[u][1] = 0;
}
mint ans = f(0, 0, -1) + f(0, 1, -1);
cout << ans.val() << endl;
return 0;
}
```
## Q. [Flowers](https://atcoder.jp/contests/dp/tasks/dp_q)
這題是 [Weighted LIS](https://amoshyc.github.io/CPsolution/template/dp/wlis.html)。WLIS 的問題是給定二個長度為 N 的序列 A 與B，對於 A 中的每個 increasing sequence $A_{x_1}, A_{x_2}, \cdots, A_{x_l}$，都可以算出一個值 $\sum_{i=1}^l B_{x_i}$。問所有 IS 中，此值最大是多少？
設 dp[i] = maximum total value of all possible IS ending at $A_i$。枚舉各個 IS 的前一項的位置，我們得轉移：
$$
dp[i] = max\left(0, \max_{j \in [0, i), A_j < A_i} dp[j] \right) + B_i
$$
此轉移會 TLE。一個常見的優化方式是將 dp 值與他們對應的 A $(A_j, dp[j])$ 存進一個容器 $C$ 中。對此容器詢問 $A_i$，他可以回答容器裡所有 A 值小於 $A_i$ 的 dp 值中，最大是多少，即
$$
\max_{(A_j, dp[j]) \in C, A_j < A_i} dp[j]
$$
此容器可以用線段樹實現，將 A 值當作 index，線段樹存 dp 值，我們邊計算 dp 值邊更新線段樹。
此題的 $h$ 就是 WLIS 的 $A$，$a$ 是 WLIS 的 $B$。
```cpp
#include <atcoder/segtree>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 1e18;
ll op(ll a, ll b) { return max(a, b); }
ll e() { return -INF; }
using SegTree = atcoder::segtree<ll, op, e>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ll> h(N);
vector<ll> a(N);
for (int i = 0; i < N; i++) {
cin >> h[i];
}
for (int i = 0; i < N; i++) {
cin >> a[i];
}
vector<ll> dp(N);
auto seg = SegTree(N + 10);
dp[0] = a[0];
seg.set(h[0], dp[0]);
for (int i = 1; i < N; i++) {
ll prev = seg.prod(0, h[i]);
dp[i] = max(a[i], prev + a[i]);
if (dp[i] > seg.get(h[i])) {
seg.set(h[i], dp[i]);
}
}
ll ans = *max_element(dp.begin(), dp.end());
cout << ans << endl;
return 0;
}
```
## R. [Walk](https://atcoder.jp/contests/dp/tasks/dp_r)
離散數學告訴我們，$A^K$ 即為任兩點之間長度為 $K$ 的 walk 數。
以下也給出 dp 的想法：設 $dp[l, u, v]$ 為 $u$ 到 $v$ 有多少條長度為 $l$ 的 walks。
考慮這些 walks 的最後一條邊 $(x, v)$，我們得到轉移：
$$
\begin{align}
dp[l, u, v]
&= \sum_{A_{x, v} = 1} dp[l - 1, u, x] \\
&= \sum_{x = 1}^N dp[l - 1, u, x] \cdot A_{x, v}
\end{align}
$$
而這就是矩陣乘法 $dp[l] = dp[l - 1] A$，又因為 $dp[1] = A$，我們可以歸納出 $dp[l] = A^l$。
```cpp
#include <atcoder/modint>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using mint = atcoder::modint1000000007;
using vec = vector<mint>;
using mat = vector<vec>;
mat matmul(mat A, mat B) {
int n = A.size();
int m = B[0].size();
int l = B.size();
mat C(n, vec(m, 0));
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
for (int k = 0; k < l; k++) {
C[r][c] += A[r][k] * B[k][c];
}
}
}
return C;
}
mat matpow(mat A, ll k) {
int n = A.size();
auto base = A;
auto res = mat(n, vec(n, 0));
for (int i = 0; i < n; i++) {
res[i][i] = 1;
}
while (k) {
if (k & 1) {
res = matmul(res, base);
}
base = matmul(base, base);
k >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll N, K;
cin >> N >> K;
auto A = mat(N, vec(N, 0));
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int e;
cin >> e;
A[r][c] = e;
}
}
auto W = matpow(A, K);
mint ans = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
ans += W[r][c];
}
}
cout << ans.val() << endl;
return 0;
}
```
## S. [Digit Sum](https://atcoder.jp/contests/dp/tasks/dp_s)
問整數 $1$ ~ $K$ 之間，有多少個整數 $X$ 滿足：digit sum 是 $D$ 的倍數。
花了不少時間，試了各種解法，終於將這題與[另一題](https://hackmd.io/@amoshyc/BkKpztrtP#F-Valid-payments)的邏輯統一，希望能成為我 digit dp 的模版。
讓我們將 $K, X$ 表示成陣列，以 $K=2345$ 為例：
$$
\begin{array}{r}
&k_3 &k_2 &k_1 &k_0 \\
&2 &3 &4 &5 \\
&x_3 &x_2 &x_1 &x_0
\end{array}
$$
設 $dp[i, s, f]$ = number of ways to fill $x_{i - 1} \cdots x_1x_0$ such that
1. digit sum $(\sum_{j=0}^{i-1} x_j) \bmod D = s$
2. $(f = 0): x_{i-1} \cdots x_1 x_0 \le k_{i-1} \cdots k_1 k_0$
$(f = 1): x_{i-1} \cdots x_1 x_0 \gt k_{i-1} \cdots k_1 k_0$
以 $K = 2345$ 為例，$dp[2, 0, 0]$ 代表二位數中有多少數小於或等於 45 且 digit sum $\bmod D = 0$；$dp[2, 0, 1]$ 代表二位數中有多少數大於 $45$ 且 digit sum $\bmod D = 0$；而 $(dp[2, 0, 0] + dp[2, 0, 1])$ 代表所有二位數中有多少個數的 digit sum $\bmod D = 0$。
枚舉 $x_i$ 的所有可能的值 $d (0 \le d \le 9)$，我們有以下遞推：
$$
dp[i, s, f] \to dp[i + 1, (s + d) \bmod D, f']
$$
其中 $f'$ 代表新的數字 $x_i x_{i-1} \cdots x_1 x_0$ 是不是大於 $k_i k_{i-1} \cdots k_1 k_0$。思考一下可以發現，只有當 $(d \gt k_i) \lor (d = k_i \land f = 1)$ 時 $f'$ 會是 1。題目所求為 $dp[N, 0, 0] - 1$。最後的 $-1$ 是因為 dp 會把 $X=0$ 也算是答案，但題目問得是 $1$ ~ $K$。
```python
K = [int(x) for x in reversed(input())]
N = len(K)
D = int(input())
M = 10 ** 9 + 7
# dp[i, s, f] = #ways to fill x[i - 1]...x[1]x[0] such that
# 1. digit sum mod D = s
# 2. x[i - 1]...x[1]x[0] <= k[i - 1]...k[1]k[0] (f = 0) or not (f = 1)
# By filling the digit x[i] with d (d = 0, 1, ..., 9):
# dp[i, s, f] -> dp[i + 1, (s + d) % D, f']
dp = [[[0, 0] for _ in range(D)] for _ in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
for s in range(D):
for f in range(2):
for d in range(10):
new_s = (s + d) % D
new_f = int((d > K[i]) or (d == K[i] and f == 1))
dp[i + 1][new_s][new_f] += dp[i][s][f]
dp[i + 1][new_s][new_f] %= M
print((dp[N][0][0] - 1 + M) % M) # subtract the 0
```
## T. [Permutation](https://atcoder.jp/contests/dp/tasks/dp_t)
問有多少個 $(1, 2, ..., N)$ 的 permutation `P` 滿足 `S` 描述的不等式？`S[i] = '<'` 代表 `P[i - 1]` 要小於 `P[i]`；`S[i] = '>'` 代表 `P[i - 1]` 要大於 `P[i]`。
網路上的題解我沒一個看得懂，直到看了大神 [Errichto](https://atcoder.jp/users/Errichto) 的[影片](https://www.youtube.com/watch?v=FAQxdm0bTaw&t=12912s)才終於想通：換數字！
設 $dp[i, j]$ = $(1, 2, ..., i)$ 有多少個 permutation 滿足 `S[:(i - 1)]`，且最後一項是 $j$。
以 $i = 4$ 為例，且不等式是 `>`，我們能用的數字是 1, 2, 3, 4。如果 $P_3$ = 2，即我們現在是狀態 $dp[i, 2]$，則 $P_0$, $P_1$, $P_2$ 能用的數字是 1, 3, 4，且 $P_2$ 必需為 3 或 4。這裡找不到重複子問題。
$$
\begin{array}{r}
&P_0 &P_1 &P_2 & &P_3 \\
&\text{_} &\text{_} &\text{_} &\gt &2 \\
\end{array}
$$
但若是我們想像將數字 3 換成 2，將 4 換成 3，則變成 $P_0$, $P_1$, $P_2$ 能用的數字是 $1, 2, 3$，且 $P_2$ 必需為 2 或 3，這就變成之前的狀態 $dp[i - 1, 2]$ 與 $dp[i - 1, 3]$。我們可以這樣轉換數字是因為在此題中，這種轉換不影響結果。
以公式描述，若 $P_i = j$ 且不等式是 `>` 時，$P_{i - 1}$ 可以填 $j, j + 1, \cdots, i - 1$，即
$$
dp[i, j] = \sum_{k = j}^{i - 1} dp[i - 1, k]
$$
注意包含了 $j$。同理，若 $P_i = j$ 且不等式是 `<` 時，$P_{i - 1}$ 可以填的數字是 $1, 2, \cdots, j - 1$。
$$
dp[i, j] = \sum_{k = 1}^{j - 1} dp[i - 1, k]
$$
這樣的 dp 是 $O(N^3)$，但我們可以透過對 $dp[i - 1]$ 建立前綴和，將之降為 $O(N^2)$：
```python
N = int(input())
S = input()
M = 10 ** 9 + 7
# dp[i, j] = number of permutation of (1, 2, ..., i) that satisfies s[:i - 1] and ends with j
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[1][1] = 1
for i in range(2, N + 1):
pref = [0 for _ in range(N + 1)]
pref[0] = dp[i - 1][0]
for j in range(1, N + 1):
pref[j] = (pref[j - 1] + dp[i - 1][j]) % M
for j in range(1, N + 1):
if S[i - 2] == '<':
dp[i][j] = pref[j - 1]
else:
dp[i][j] = (pref[i - 1] - pref[j - 1] + M) % M
# for j in range(1, N + 1):
# if S[i - 2] == '<':
# for k in range(1, j):
# dp[i][j] += dp[i - 1][k]
# dp[i][j] %= M
# else:
# for k in range(j, i):
# dp[i][j] += dp[i - 1][k]
# dp[i][j] %= M
print(sum(dp[N][j] for j in range(1, N + 1)) % M)
```
## U. [Grouping](https://atcoder.jp/contests/dp/tasks/dp_u)
給定 $N \times N$ 矩陣 $A$，$A_{i, j}$ 代表將 Rabbit $i$ 與 Rabbit $j$ 分在同一組時的得分。現將 $N$ 隻 Rabbits 分成一或多組，請最大化得分的總和。
設 $dp[S]$ 代表將 Rabbit 集合 $S$ 分成一或多組的得分。S 可能是一或多個組，讓我們枚舉其中的一組 $T$ 的所有可能，得到：
$$
dp[S] = \max_{\forall T \subset S} \left(dp[S - T] + score[T] \right)
$$
其中 $score[T]$ 可以預先計算好。實作上，枚舉子集合的方法可參[這裡](https://cp-algorithms.com/algebra/all-submasks.html)，整體時間 $O(2^N N^2) + O(3^N)$。
```python
N = int(input())
M = 10 ** 9 + 7
A = [[int(x) for x in input().split()] for _ in range(N)]
score = [0 for _ in range(1 << N)]
for s in range(1 << N):
for i in range(N):
if s & (1 << i):
for j in range(i + 1, N):
if s & (1 << j):
score[s] += A[i][j]
dp = [0 for _ in range(1 << N)]
for s in range(1 << N):
t = s
while t:
dp[s] = max(dp[s], dp[s - t] + score[t])
t = (t - 1) & s
print(dp[(1 << N) - 1])
```
## V. [Subtree](https://atcoder.jp/contests/dp/tasks/dp_v)
給定一棵樹，將每個節點塗成黑色或白色，且滿足：任何黑色節點可以只經由黑色節點到達其他黑色節點。問對每個節點 $v$ 來說，若 $v$ 是黑色的，整棵樹有多少種塗法？
若只要考慮樹根 $root$ 是黑色時的塗法，那這題我們會做。可以想像，若是合法的塗法，黑色的節點都會在樹根的部份，不會出現 parent 是白色的黑色節點，因為不滿足題意。
設 $dp[u]$ 代表樹根是 $root$、且 $u$ 塗成黑色時，子樹 $u$ 的方法數。考慮 $u$ 的 children 要塗成白色或黑色，我們得到以下轉移：
$$
dp[u] = \prod_{v \in child(u)} (1 + dp[v])
$$
其中的 $1$ 代表節點 $v$ 是塗成白色的方法數；$dp[v]$ 是 $v$ 是黑色時，子樹 $v$ 的方法數。但這個 dp 只能告訴我們 $root$ 的答案，我們當然都可以將每個節點都當 $root$ 跑一次 dp，求出該節點的答案，但明顯會 TLE。
事實上，我們可以透過一些組合，將非 $root$ 節點的答案求出，不用真的每個節點都當 $root$ 跑一次 dp。如下圖，這是以節點 0 為 $root$ 的 dp：
```graphviz
graph {
node [fontname="Arial" ];
size = "3!";
0 [color="red" xlabel="16"];
1 [color="red" xlabel="1"];
2 [color="red" xlabel="1"];
3 [color="black" xlabel="3"];
4 [color="blue" xlabel="2"];
5 [color="blue" xlabel="1"];
0 -- {1, 2, 3};
3 -- {4};
4 -- {5};
}
```
對於非 $root$ 的節點 3，我們可以將之想成是 $root$，而紅色部份是節點 3 除了子樹 4（藍色部份）以外的另一個子樹，而紅色部份的方法數是：
$$
\prod_{v \in child(0), v \ne 3} (1 + dp[v]) = (1 + dp[1]) (1 + dp[2]) = 4
$$
由此我們就能算出若節點 3 是 $root$ 時，他的答案（也是 dp 值）是 $(1 + red)(1 + blue) = (1 + 4)(1 + 2) = 15$。同理其他非 $root$ 節點 $u$，也是將 $u$ 的 parent 視為 $u$ 的另一個子樹，以此來求出將 $u$ 視為 $root$ 時的答案。
實作上，使用兩次 DFS 並搭配 prefix, suffix product 來高速求積，使用 pypy 會有三個 testcases [TLE](https://atcoder.jp/contests/dp/submissions/19095888)，因此使用 C++。
```cpp
#include <iostream>
#include <vector>
#define sz(x) (int(x.size()))
using namespace std;
using ll = long long;
const int MAX_N = 100000;
ll N, mod;
ll dp[MAX_N];
ll ans[MAX_N];
vector<int> adj[MAX_N];
ll build(int u, int p) {
dp[u] = 1;
for (int v: adj[u]) {
if (v != p) {
dp[u] *= (1 + build(v, u));
dp[u] %= mod;
}
}
return dp[u];
}
void solve(int u, int p, ll top) {
vector<ll> branches;
for (int v : adj[u]) {
if (v == p) {
branches.push_back(1 + top);
} else {
branches.push_back(1 + dp[v]);
}
}
if (sz(branches) == 0) {
ans[u] = 1;
return;
}
vector<ll> pref(sz(branches), 1);
vector<ll> suff(sz(branches), 1);
pref.front() = branches.front() % mod;
for (int i = 1; i < sz(branches); i++) {
pref[i] = (pref[i - 1] * branches[i]) % mod;
}
suff.back() = branches.back() % mod;
for (int i = sz(branches) - 2; i >= 0; i--) {
suff[i] = (suff[i + 1] * branches[i]) % mod;
}
ans[u] = pref.back();
for (int i = 0; i < sz(adj[u]); i++) {
int v = adj[u][i];
if (v != p) {
ll prod1 = ((i > 0) ? pref[i - 1]: 1);
ll prod2 = ((i != sz(branches) - 1) ? suff[i + 1]: 1);
solve(v, u, (prod1 * prod2) % mod);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> mod;
for (int i = 0; i < N - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
build(0, -1);
solve(0, -1, 0);
for (int i = 0; i < N; i++) {
cout << ans[i] << "\n";
}
return 0;
}
```
:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::
Sign in with Wallet
Connect another wallet