【板子】拓扑序计数

题目通过逆序对约束建立了一个有向无环图DAG要求计算这个 DAG 所有可能的拓扑序数量。这是图论中一个非常经典的问题。给定一个有向无环图DAG包含 n 个节点和 m 条有向边。求从节点 1 到节点 n 的所有拓扑序数量即满足所有边约束的全排列数量。答案对 998244353 取模。输入格式第一行n, m接下来 m 行每行 u, v 表示一条从 u 到 v 的有向边输出格式一个整数表示拓扑序数量核心思路用pre[i]存i的所有前驱节点。dp[mask]表示当前已经放了mask二进制状态里的这些数有多少种合法方案。枚举mask尝试放一个新的节点j。如果j的所有前驱都已经在mask里了就可以放j。代码#include bits/stdc.h using namespace std; const int MOD 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; // pre[j] 所有必须在 j 前面的节点列表 vectorvectorint pre(n); for (int i 0; i m; i) { int u, v; cin u v; u--; v--; // 转为 0-based pre[v].push_back(u); // u 是 v 的前驱 } // dp[mask] 当前选中集合为 mask 时的方案数 vectorint dp(1 n, 0); dp[0] 1; // 初始状态一个数都没放算 1 种方案 // 枚举所有状态 for (int mask 0; mask (1 n); mask) { // 尝试放下一个节点 j for (int j 0; j n; j) { // 如果 j 已经放过了跳过 if (mask j 1) continue; // 检查 j 的所有前驱是否都已经放过 bool ok true; for (int p : pre[j]) { if (!(mask p 1)) { ok false; break; } } // 如果前驱齐全可以放 j if (ok) { int next_mask mask | (1 j); dp[next_mask] (dp[next_mask] dp[mask]) % MOD; } } } // 答案所有节点都放完了的状态 cout dp[(1 n) - 1] \n; return 0; }