\(\text{DP}\) 基础
本文记录了一些基础的 \(\text{DP}\) 以及一些优化技巧。
状压 \(\text{DP}\)
状压 \(\text{DP}\) 与其说是一种 \(\text{DP}\)，不如说是一种暴搜的技巧，通过把 \(01\) 状态压缩进一个支持快速枚举和比较的集合中（例如 \(32\) 位整数或 std::bitset）来实现优化复杂度的一个 \(\text{trick}\)。
状压 \(\text{DP}\) 与位运算强关联，位运算相关的技巧可以见 GCC tricks。
一些位运算常见的技巧：
- 对于集合中的元素，最好在一开始读入的时候就以 \(\text{0-index}\) 读入，这样便于压缩进二进制集合中。
[SCOI2005] 互不侵犯
题意：在 \(n \times n\) 的国际象棋的棋盘里面放 \(m\) 个国王，使他们互不攻击，共有多少种摆放方案。
定义 \(f_{i, j, k}\) 为设定完前 \(i\) 行，第 \(i\) 行的压缩状态为 \(j\)，目前已经设定好了 \(m\) 个国王的方案数。
考虑什么时候可以转移，定义当前行的状态为 \(j\)，上一行的转移为 \(k\)。
- 如果 \([j \And k \ll 1][j \And k][j \And k \gg 1] = 0\)，则说明 \(k\) 与 \(j\) 左中右三格之内没有交集，即这一行的每一个国王都不在上一行国王能吃的范围内，意味可以进行转移：
- 否则则说明这一行的国王会与上一行的国王冲突，转移不能进行。
讲一讲这题的特殊的 \(\text{trick}\)：
注意到有许多状态在行这个层面本身就是不合法的，例如 \(\text{101010*11*0101}\)，只要二进制位上有相邻的位被置位，则该状态不合法。
因此，我们可以先做一个预处理，筛选出所有合法的状态，在每一轮转移时，直接枚举合法的状态即可。
更进一步，我们其实还可以预处理出对于任意一个状态 \(j\)，它可以转移到的合法状态 \(k\)。
时间复杂度不太好分析，其上界为 \(O(nm \times 2 ^ {2n})\)，但实际上远优于该时间复杂度，简称其为 \(O(\text{能过})\)。
代码：
#include <bits/extc++.h>
#define inline __always_inline
#define popcnt(x) __builtin_popcount(x)
template <typename T> inline void read(T &x)
{char ch;for (ch = getchar(); !isdigit(ch); ch = getchar());for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
const int MaxN = 10, MaxA = 1 << 9, MaxM = 85;int n, m, mask, cnt = 0, s[MaxA];
std::vector<int> trans[MaxA];
int64_t f[MaxN][MaxA][MaxM];
int main()
{read(n), read(m);mask = (1 << n) - 1;for (int x = 0; x <= mask; x++)if (!(x & (x << 1 | x >> 1)))f[1][cnt][popcnt(x)] = 1, s[cnt++] = x;for (int j = 0; j < cnt; j++)for (int k = 0; k < cnt; k++)if (!(s[k] & (s[j] << 1 | s[j] | s[j] >> 1)))trans[j].push_back(k);for (int i = 2; i <= n; i++)for (int j = 0; j < cnt; j++)for (auto &&k : trans[j])for (int t = popcnt(s[k]); t <= m; t++)f[i][k][t] += f[i - 1][j][t - popcnt(s[k])];int64_t ans = 0;for (int x = 0; x < cnt; x++) ans += f[n][x][m];printf("%ld", ans);return 0;
}
[POI2004] PRZ
定义 \(f_i\) 为集合 \(i\) 所包含的所有队员过桥的最小时间，则容易推出转移：
其中 \(i - j\) 代表集合减，在代码实现中可以用 \(i \oplus j\) 实现，对于 \(W(x)\) 和 \(T(x)\) 这两个函数可以先预处理出集合函数的值。
如果预处理不影响代码的时间复杂度，可以预处理出尽可能多的常用信息以减小常数，简化编码。
预处理 \(W(x)\) 和 \(T(x)\) 的代码如下：
#define MSB(x) std::__lg(x)
for (int i = 1; i <= mask; i++)
{T[i] = std::max(T[i ^ 1 << MSB(i)], t[MSB(i)]);W[i] = W[i ^ 1 << MSB(i)] + w[MSB(i)];
}
其中 \(\operatorname{MSB}(x)\) 返回 \(x\) 的最高有效位，从而实现集合递推。
本题还用到了一个 \(\text{trick}\)：子集枚举。
对于一个二进制集合 \(i\)，枚举其所有的子集 \(j\) 的代码如下：
for (int j = i - 1 & i; ; j = j - 1 & i)
{// do something here.if (!j) break;
}
上述算法等效于忽略了 \(i\) 在二进制中的所有的 \(0\)，直接向 \(1\) 的有效位借位，从而实现枚举子集，时间复杂度为 \(O(3 ^ n)\)。
总代码：
#include <bits/extc++.h>#define inline __always_inline
#define MSB(x) std::__lg(x)
template <typename T> inline void chkmin(T &x, const T &y) { if (x > y) x = y; }
template <typename T> inline void read(T &x)
{char ch;for (ch = getchar(); !isdigit(ch); ch = getchar());for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
const int MaxN = 16, MaxS = 1 << MaxN;int m, n, mask, t[MaxN], w[MaxN], T[MaxS], W[MaxS], f[MaxS];
int main()
{read(m), read(n), mask = (1 << n) - 1;for (int i = 0; i < n; i++) read(t[i]), read(w[i]);for (int i = 1; i <= mask; i++){T[i] = std::max(T[i ^ 1 << MSB(i)], t[MSB(i)]);W[i] = W[i ^ 1 << MSB(i)] + w[MSB(i)];}memset(f, 0x3f, sizeof(f)), f[0] = 0;for (int i = 1; i <= mask; i++)for (int j = i - 1 & i; ; j = j - 1 & i){if (W[i ^ j] <= m) chkmin(f[i], f[j] + T[i ^ j]);if (!j) break;}printf("%d", f[mask]);return 0;
}
花园
小 L 有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为 \(1 \sim n\)。花园 \(1\) 和 \(n\) 是相邻的。
任意相邻 \(m\) 个花圃中都只有不超过 \(k\) 个 C 形的花圃，其余花圃均为 P 形的花圃。
请帮小 L 求出符合规则的花园种数对 \(10 ^ 9 + 7\) 取模的结果。
\(2 \leq n \le 10^{15}\)，\(2 \leq m \leq \min(n, 5)\)，\(1 \leq k \lt m\)。
本题的 \(\text{DP}\) 推导私以为很有难度，先考虑朴素的 \(\text{DP}\) 怎么做。
定义 \(f_{i, j}\) 为前 \(i - 1\) 个花圃已种完，以第 \(i\) 个花圃为起点，后 \(m\) 个花圃对应的状态集合是 \(j\) 的方案数。
稍加思考可以推出转移：
考虑如何统计答案，这里需要注意一个 误区，直接统计 \(\sum_i f_{n, i}\) 是错误的，因为初始状态为 \(i\) 的中间量可以从初始状态为 \(j\) 的中间量转移，使得答案混在一起。
正确的做法是枚举每一种初始状态 \(i\)，独立地跑一遍 \(\text{DP}\)，并累加 \(f_{n, i}\)。
同时还可以利用滚动数组压缩一维，就可以取得 \(\text{80 pts}\) 的好成绩，时间复杂度 \(O(2 ^ {2m} \times n)\)
#include <bits/extc++.h>#define inline __always_inline
#define popcnt(x) __builtin_popcount(x)
template <typename T> inline void read(T &x)
{char ch;for (ch = getchar(); !isdigit(ch); ch = getchar());for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
const int MaxN = 1e5 + 5, MaxM = 5, MaxA = 1 << MaxM, mod = 1e9 + 7;int64_t n;
int m, k, mask, s[MaxA], cnt = 0, f[2][MaxA];
int main()
{read(n), read(m), read(k), mask = (1 << m) - 1;for (int i = 0; i <= mask; i++)if (popcnt(i) <= k) s[cnt++] = i;int ans = 0;for (int t = 0; t < cnt; t++){memset(f[0], 0, sizeof(f[0])), f[0][s[t]] = 1;for (int i = 1; i <= n; i++){int prev = i - 1 & 1, next = i & 1;memset(f[next], 0, sizeof(f[next]));for (int j = 0; j < cnt; j++){int x = s[j] >> 1 | 1 << m - 1;(f[next][s[j]] += f[prev][s[j] >> 1]) %= mod;if (popcnt(x) <= k)(f[next][s[j]] += f[prev][x]) %= mod;}}(ans += f[n & 1][s[t]]) %= mod;}printf("%d", ans);return 0;
}
考虑进一步优化，由于 \(n\) 的值域巨大，因此考虑矩阵快速幂。
矩阵快速幂只需要使用普通的 \((\times, +)\) 矩阵即可。
注意任何矩阵快速幂，如果乘法过程中有可能爆 \(32\) 位整数，即使初始值设定是 \(01\) 矩阵也一定要开 long long，因为在数次乘法之后，矩阵中的值可能非常大。
#include <bits/extc++.h>#define inline __always_inline
#define popcnt(x) __builtin_popcount(x)
template <typename T> inline void read(T &x)
{char ch;for (ch = getchar(); !isdigit(ch); ch = getchar());for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
const int MaxN = 1e5 + 5, MaxM = 5, MaxA = 1 << MaxM, mod = 1e9 + 7;int64_t n;
int m, k, mask, s[MaxA], cnt = 0, f[2][MaxA];
struct vector_t
{int v[MaxA];inline void clear() { memset(v, 0, sizeof(v)); }inline auto &operator[](int x) { return v[x]; }inline const auto &operator[](int x) const { return v[x]; }
} v;
struct matrix_t
{int M[MaxA][MaxA];inline void unit() { for (int i = 0; i < MaxA; i++) M[i][i] = 1; }inline void clear() { memset(M, 0, sizeof(M)); }inline auto &operator[](int x) { return M[x]; }inline const auto &operator[](int x) const { return M[x]; }
} trans;
inline matrix_t operator*(const matrix_t &x, const matrix_t &y)
{matrix_t m; m.clear();for (int i = 0; i < MaxA; i++)for (int k = 0; k < MaxA; k++)for (int j = 0; j < MaxA; j++)m[i][j] = (m[i][j] + 1l * x[i][k] * y[k][j]) % mod; // 不开 long long 见祖宗！！！return m;
}
inline vector_t operator*(const matrix_t &x, const vector_t &y)
{vector_t v; v.clear();for (int i = 0; i < MaxA; i++)for (int j = 0; j < MaxA; j++)v[i] = (v[i] + 1l * x[i][j] * y[j]) % mod;return v;
}
inline matrix_t operator^(matrix_t x, int64_t n)
{matrix_t m; m.clear(), m.unit();for (; n; n >>= 1, x = x * x)if (n & 1) m = m * x;return m;
}int main()
{read(n), read(m), read(k), mask = (1 << m) - 1;for (int i = 0; i <= mask; i++)if (popcnt(i) <= k){s[cnt++] = i;trans[i][i >> 1] = 1;int j = i >> 1 | 1 << m - 1;if (popcnt(j) <= k)trans[i][j] = 1;}trans = trans ^ n;int ans = 0;for (int t = 0; t < cnt; t++){v[s[t]] = 1;(ans += (trans * v)[s[t]]) %= mod;v[s[t]] = 0;}printf("%d", ans);return 0;
}
