更佳的阅读体验：2023 国庆集训 Day 4A 笔记，本文同步发表于 洛谷博客。

以下内容为个人总结，如有错误或您有不同见解，欢迎指出。

状压 DP

洛谷 P4363 - 一双木棋

• 只需要将当前局面下所放棋子的轮廓线压入状态即可，DP 初值为 $f[整个棋盘] = 0$。
• 状压当前的轮廓线，依据这一步该谁下进行 min / max 搜索。

洛谷 P5369 - 最大前缀和

• 统计每个子集作为最大前缀和的次数。
• 如果某个前缀和是最大前缀和，那么这个前缀的所有后缀和都 $> 0$，后面的所有前缀和都 $\le 0$。
• 设 $f[S]$ 为将 $S$ 排列成所有后缀 $> 0$ 的方案数，$g[S]$ 为将 $S$ 排列成所有前缀 $\le 0$ 的方案数。
• 答案即为 $\sum sum[S]f[S]g[U-S]$，$U$ 为全集。

洛谷 P5492 - 随机算法

• 求图上最大独立集。
• 设 $f[S]$ 为 $S$ 内随机一个排列的正确方案数。
• 枚举 $S$ 排列的第一个元素 $x$，加入 $x$ 会导致删除 $x$ 及与其相邻的点集 $c_x$。
• 那么如果 $max⁡[S]=max⁡[S-c_x ]+1$，就令 $f[S]$ 加上 $f[S-c_x]$ 。

int ctz[1 << N];
long long f[1 << N], g[1 << N];
long long c[N];
const long long p = 998244353;

cin >> n >> m;

for (int i = 0; i < m; i++) {
    cin >> x >> y;
    c[x] |= 1 << y;
    c[y] |= 1 << x;
}

for (int i = 0; i < n; i++) {
    ctz[1 << i] = i;
}

for (int S = 1; S < 1 << n; S++) {
    int x = ctz[S & -S];
    g[S] = max(g[S - (1 << x)], g[S - (1 << x) - (c[x] & S)] + 1);
}

f[0] = 1;
for (int S = 1; S < 1 << n; S++) {
    for (int x = 0; x < n; x++) {
        if (~S >> x & 1) <=> if (!(S >> x & 1))
            continue;
        if (g[S - (1 << x) - (c[x] & S)] + 1 < g[S])
            continue;
        f[S] = (f[S] + f[S - (1 << x) - (c[x] & S)]) % p;
    }
}

cout << f[(1 << n) - 1] /n! << endl; 

图上拓扑序计数

给定一张 DAG，求其合法拓扑序个数。$n \le 20$，$m \le \frac{n(n - 1)}{2}$。

• 设 $f(S)$ 表示 $S$ 诱导子图的拓扑序个数。
• 转移时，枚举 $S$ 中拓扑序最靠前的节点 $i$：$f(S) = \sum_{i \in S, ind_i = 0}f(S-\{i\})$ 。其中 $ind_i=0$ 表示 $i$ 在 $S$ 中没有入度（而非整个图中）。

// topo count

long long f[1 << N];

bool valid(int x, int s) {
    // s 没有连向 x 的边
}

for (int s = 1; s < 1 << n; ++s) {
    for (int x = 0; x < n; ++x) {
        if (~s >> x & 1) continue;
        if (valid(x, s)) f[s] += f[s - (1 << x)];
    }
}

边子集拓扑序计数

给定一张有向图（不保证是 DAG）。设其边集为 $E$ 。对于 $T \subseteq E$ 定义 $f(T)$ 为保留 $T$ 时整张图的拓扑序数量，求 $∑_{T \subseteq E}f(T)$。$n \le 20$，$m \le n(n-1) $。

• 设 $g(S)$ 表示 $S$ 诱导子图的答案，我们输出 $g(U)$。
• 与其统计每个边集 $T$ 的拓扑序方案数，不如统计每种拓扑序能在多少种 $T$ 下合法。
• 转移时仍然枚举 $S$ 中拓扑序最靠前的节点 $i$ 。
• 要想让 $i$ 最靠前合法，就需要让 $i$ 在 $S$ 内的 $ind=0$。换句话说，不能保留从 $S-\{i\}$ 连向 $i$ 的边，而 $i$ 连向 $S-\{i\}$ 的边可以任意保留。
• 所以 $g(S) = \sum_{i \in S} f(S-\{i\}) 2^{cnt_{i,S-\{i\}}}$，其中 $cnt_{i,S-{i}}$ 表示 $i$ 连向 $S-\{i\}$ 的边数。

// topo count with edge subset

long long count[N][1 << N];

cin >> n >> m;

for (int i = 0; i < m; ++i) {
    cin >> x >> y;
    for (int s = 1; s < 1 << n; ++s)
        if (s >> y & 1) ++count[x][s];
}

for (int s = 1; s < 1 << n; ++s)
    for (int x = 0; x < n; ++x) {
        if (~s >> x & 1) continue;
        f[s] += f[s - (1 << x)] << count[x][s - (1 << x)];
    }

洛谷 P2831 - 愤怒的小鸟

• 每个优的抛物线至少经过两只猪。用 $\begin{cases} y_1 = ax_1^2 + bx_1 \\ y_2 = ax_2^2 + bx_2 \end{cases}$ 可解出一组 $(a, b)$。共有 $O(n^2)$ 组。预处理出每两只猪 $(i, j)$ 形成的抛物线能消灭哪些猪 $c[i][j]$ 。
• 设 $f[S]$ 为消灭 $S$ 集合猪最少需要多少只小鸟。枚举第一条抛物线，则 $f[S] = \min⁡(f[S-c[i][j]]+1)$。
• 固定 $i$ 为 $S$ 中的最小元，则只需枚举 $j$ 即可。
• 复杂度为 $O(n2^n)$。

洛谷 P3959 - 宝藏

• 对于 $v$ 相等的部分分，可以使用贪心求解。
• 状态中需记录当前层数。设 $f[x][i][S]$ 为 $x$ 的子树编号集合为 $S$，$x$ 在第 $i$ 层的最小子树代价。
• 得到转移方程 $f[x][i][S] = \min⁡(f[x][i][T]+f[y][i+1][S-T]+dis(x,y) \times i)$。
• 取答案时枚举每个点作为起始点。