太可怕了！2025 年才过去 4 个月，正经文章的总数已经和 2024 年中正经文章的总数一样多了。
有标号无向图计数
问题模型大概如下：
给定 \(N\) 个点，你可以在它们间任意连边，但存在限制：
- 其中一个较好处理（如要求图必须是二分图）；
- 另一个较难处理（如去重问题等）；
- 最后，可能要求图连通。
首先需要知道怎么处理这样的计数问题。以下皆建立在无重边、自环的基础上。
先只考虑容易的限制，且不要求连通：
注：如果发现 不连通 的时候没办法很方便地计算精确方案数（也就是说会算重），那么可以把 去重 作为较难的限制，这一步算重就不重要了。
该怎么求怎么求。例如，若该限制是二分图且可以算重，枚举左部点数及边，那么方案数就是 \(\sum\limits_{i=0}^n C_n^i\cdot C_{i\cdot (n-i)}^m\)。
这个时候需要注意到算重部分的意义是什么。比如此处，计算中一个连通块将左右部翻转后被视作不同的子图，但在全局看来对应的总图是同一个二分图。因此，对于拥有 \(k\) 个连通块的图，其被计算了 \(2^k\) 次。再加上必须连通的限制，仍只考虑容易的限制：
如果不存在其他限制，那么就是 A001187。
连通的方案就是任意的方案减去不连通的方案。
- 任意的求法就是第一点；
- 不连通的方案，枚举 \(1\) 所在子集，让其补集里面任意连边（第 1 点的子问题）且不和 \(1\) 所在子集相连。
接着，对连通的情况应用较难处理的限制：
因为连通会带来一些比较好的性质简化运算，所以选择在这一步加上较难的限制。
例如，对于上文中二分图去重的例子，连通图中显然只有一个连通块，将连通图的方案 \(\div 2\) 就可以得到答案。最后，如果题目要求任意图的方案，用第三步中的答案再次算出任意图的答案。
相当于是把第 2 点中的过程反过来，枚举 \(1\) 所在子集，在其补集中任意连边（该问的子问题）且可以和 \(1\) 所在的子集连边。
这样就可以解决问题。
A - Many Good Tuple Problems
https://atcoder.jp/contests/abc327/tasks/abc327_g
如果把一组 \((S_i,T_i)\) 看作一条边的话，原限制就可以转化为：在 \(N\) 个点中连 \(M\) 条可重边，形成二分图的方案数。边有序。
你可以发现我偷懒把这道题拿去上面举例了，由于边是可重的，而我们的模型要求无重边，但发现这个限制是独立于模型外的，也就是可以在最后枚举有多少条不同边，再用一点组合手段计算实际贡献。
首先令 \(f_{0,n,m}\) 表示 \(n\) 个点、\(m\) 条边、不去重、连通性任意 的方案数，那么 \(f_{0,n,m}=\sum_{i=0}^n C_n^i\cdot C_{i\cdot (n-i)}^m\)。
令 \(f_{1,n,m}\) 表示 不去重、要求 连通 的方案，那么有 \(f_{1,n,m}=f_{0,n,m}-\sum\limits_{i,j} C_{n - 1}^{i-1}\cdot f_{1,i,j}\cdot f_{0,n-i,m-j}\)。
令 \(f_{2,n,m}\) 表示 去重，要求 连通 的方案，那么有 \(f_{2,n,m}=\dfrac {f_{1,n,m}}{2}\)。
令 \(f_{3,n,m}\) 表示 去重，连通性任意 的方案数，那么有 \(f_{3,n,m}=\sum\limits_{i,j} C_{n-1}^{i-1} \cdot f_{2,i,j} \cdot f_{3,n-i,m-j}\)。
最后的方案数为 \(\sum\limits_{j} f_{3,n,j}\cdot F(m,j)\)。其中 \(F(m,j)\) 表示把 \(m\) 个有标号的球放在 \(j\) 个有标号的盒子里，不空放的方案数，可以容斥。最后注意边反向算两种，所以乘上 \(2^m\)。
复杂度 \(O(n^6)\)。
#include <bits/stdc++.h>
const int mod = 998244353;
const int inv2 = (mod + 1) >> 1;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, M, m;
std::cin >> n >> M, m = std::min(n * (n - 1) / 2, M);
std::vector<std::vector<long long> > C(n * n + 1, std::vector<long long> (n * n + 1));
for (int i = 0; i <= n * n; ++i) {
C[i][0] = 1ll;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
std::vector<std::vector<std::vector<long long> > > f(4, std::vector<std::vector<long long> > (n + 1, std::vector<long long> (m + 1)));
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m && j <= i * (i - 1) / 2; ++j)
for (int k = 0; k <= i; ++k)
(f[0][i][j] += C[i][k] * C[k * (i - k)][j]) %= mod;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j) {
auto t(0ll);
for (int k = 1; k <= i; ++k)
for (int l = 0; l <= j; ++l)
(t += C[i - 1][k - 1] * f[1][k][l] % mod * f[0][i - k][j - l]) %= mod;
f[1][i][j] = (f[0][i][j] + mod - t) % mod;
f[2][i][j] = f[1][i][j] * inv2 % mod;
}
f[3][0][0] = 1ll;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= m; ++j)
for (int k = 1; k <= i; ++k)
for (int l = 0; l <= j; ++l)
(f[3][i][j] += C[i - 1][k - 1] * f[2][k][l] % mod * f[3][i - k][j - l]) %= mod;
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
std::vector<long long> F(m + 1);
for (int i = 1; i <= m; ++i) {
F[i] = qkp(i, M);
for (int j = 1, p = mod - 1; j < m; ++j, p = mod - p)
(F[i] += p * C[i][j] % mod * qkp(i - j, M)) %= mod;
}
auto res(0ll);
for (int j = 1; j <= m; ++j)
(res += f[3][n][j] * F[j]) %= mod;
std::cout << res * qkp(2, M) % mod << '\n';
return 0;
}B - Many MST
https://atcoder.jp/contests/abc386/tasks/abc386_g
这里需要注意到 MST 和连通块的隐含联系。按照 Kruskal 的生成方式可以发现只需要在合并两个连通块时加上它们之间连边中最小的边权就可以得到 MST。
因此容易想到在 DP 时对最小边权进行限制；枚举 \(k\)，让边权 \(\le k\) 成为简单限制；让求解 MST 成为某种意义上的较难限制。
令 \(f_{0,n,k}\) 表示 \(n\) 个点，边权 \(\le k\)、对连通性没有要求 的方案数；相应地，\(f_{1,n,k}\) 表示 要求连通 的方案数，则：
\(f_{0,n,k}=\sum\limits_i C_{n-1}^{i-1}\cdot f_{1,i,k-1} \cdot f_{0,n-i,k}\cdot (M-k+1)^{i\times(n-i)}\)。
注解：式子正确性建立在 \(1\) 所在 的由权值 \(<k\) 的边构成的最大连通块 大小为 \(i\) 的基础之上，故两个连通块之间的边权只能 \(\ge k\)。这也提醒我们，此处的 不连通 含义实际上是给这些边一个 \((M-k)\) 的系数。
那么这样你会注意到，\(f_0\) 的意义就与 \(k\) 无关了（那么显然值也与 \(k\) 无关），但是仍然保留 \(k\) 对思考有帮助，故留之。\(f_{1,n,k}=f_{0, n, k} - \sum\limits_i C_{n - 1}^{i-1} \cdot f_{1,i,k}\cdot f_{0,n-i,k}\times (M-k)^{i\times (n - i)}\)。
令 \(g_{0, n, k}\) 表示 \(n\) 个点、边权 \(\le k\)、对连通性没有要求 的 MST 之和；相应地，\(g_{1,n,k}\) 表示对应条件下 要求连通 的 MST 之和。则：
\(g_{0,n,k}=\sum\limits_{i} C_{n-1}^{i-1}\cdot (f_{1,i,k - 1}\cdot g_{0,n-i,k}+g_{1,i,k - 1} \cdot f_{0,n-i,k}+f_{1,i,k-1}\cdot f_{0,n-i,k}\cdot k)\cdot (M-k+1)^{i\times (n-i)}\)。
注解：类比 \(f_0\) 的计算方式得到 \(g_0\)。在 \(i\times (n-i)\) 中任选一条作为 MST 上权值为 \(k\) 的边，故有 \(f_{1,i,k-1}\cdot f_{0,n-i,k}\cdot k\)。之所以必须要求有这么一条边是为了和 \(g_{k-1}\) 和 \(g_{k+1}\) 等区分。\(g_{1,n,k}=g_{0,n,k}-\sum\limits_i C_{n-1}^{i-1}\cdot (f_{1,i,k}\cdot g_{0,n-i,k}+g_{1,i,k}\cdot f_{0,n-i,k}+f_{1,i,k}\cdot f_{0,n-i,k}\cdot k)\cdot (M-k)^{i\times (n-i)}\)。
复杂度 \(O(n^2\cdot M)\)。要求预处理幂，不然会 T。以及可能需要把 \(f_0,f_1,g_0,g_1\) 放在同一个内层循环求，不然会卡常；在此基础上使用内存连续访问优化似乎并不明显 
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int N, M;
std::cin >> N >> M;
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
crr f(2, brr(N + 1, arr(M + 1))), g(2, brr(N + 1, arr(M + 1)));
brr C(N + 1, arr(N + 1)), p(M + 1, arr(N * N + 1));
for (int i = 0; i <= M; ++i) {
p[i][0] = 1ll;
for (int j = 1; j <= N * N; ++j)
p[i][j] = p[i][j - 1] * i % mod;
}
for (int i = 0; i <= N; ++i) {
C[i][0] = 1ll;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
f[1][0][0] = f[1][1][0] = 1ll;
for (int n = 1; n <= N; ++n)
for (int k = 1; k <= M; ++k) {
f[0][n][k] = f[1][n][k - 1];
for (int i = 1; i < n; ++i) {
(f[0][n][k] += C[n - 1][i - 1] * f[1][i][k - 1] % mod * f[0][n - i][k] % mod * p[M - k + 1][i * (n - i)]) %= mod;
(f[1][n][k] += mod - C[n - 1][i - 1] * f[1][i][k] % mod * f[0][n - i][k] % mod * p[M - k][i * (n - i)] % mod) %= mod;
}
(f[1][n][k] += f[0][n][k]) %= mod;
}
for (int n = 1; n <= N; ++n)
for (int k = 1; k <= M; ++k) {
g[0][n][k] = g[1][n][k - 1];
for (int i = 1; i < n; ++i) {
(g[0][n][k] += (f[1][i][k - 1] * g[0][n - i][k] % mod + g[1][i][k - 1] * f[0][n - i][k] % mod + f[1][i][k - 1] * f[0][n - i][k] % mod * k) % mod * C[n - 1][i - 1] % mod * p[M - k + 1][i * (n - i)]) %= mod;
(g[1][n][k] += mod - (f[1][i][k] * g[0][n - i][k] % mod + g[1][i][k] * f[0][n - i][k] % mod + f[1][i][k] * f[0][n - i][k] % mod * k) % mod * C[n - 1][i - 1] % mod * p[M - k][i * (n - i)] % mod) %= mod;
}
(g[1][n][k] += g[0][n][k]) %= mod;
}
// for (int n = 1; n <= N; ++n)
// for (int k = 1; k <= M; ++k) {
// printf("f[0][%d][%d] = %lld\n", n, k, f[0][n][k]);
// printf("f[1][%d][%d] = %lld\n", n, k, f[1][n][k]);
// printf("g[0][%d][%d] = %lld\n", n, k, g[0][n][k]);
// printf("g[1][%d][%d] = %lld\n", n, k, g[1][n][k]);
// }
std::cout << g[1][N][M] << '\n';
return 0;
}有标号 DAG 计数
给定 \(N\) 个点，你可以在它们间任意连边，要求最后图为 DAG，可能要求图弱连通。
如果说无向图计数关键在于连通块，那么 DAG 在此基础上关键在于入度为 \(0\) 的点集。
令 \(f(i)\) 表示 \(i\) 个点的 DAG 的答案；\(g_{0, i,j}\) 表示 \(i\) 个点的 DAG，其中 \(j\) 个入度为 \(0\) 的方案，不难想到容斥：令 \(g_{1,i,j}\) 表示至少 \(j\) 个的方案，那么：
\[ g_{1,i,j}=C_i^j\times f(i-j)\times 2^{j\times (i-j)}\\ g_{0,i,j}=\sum_{k=j}^i (-1)^{k-j}\cdot C_k^j\cdot g_{1,i,j}\\ f(i)=\sum_{j=1}^i g_{0,i,j} \]
整理有：
\[ \begin{aligned} f(i) &=\sum_{j=1}^i \sum_{k=j}^i (-1)^{k-j}\cdot C_k^j\cdot g_{1,i,k}\\ &=\sum_{k=1}^i (-1)^k\cdot g_{1,i,k}\cdot \sum_{j=1}^k (-1)^j\cdot C_k^j\\ &=\sum_{k=1}^i (-1)^k\cdot g_{1,i,k}\cdot (0^k-1)\\ &=\sum_{k=1}^i (-1)^{k+1}\cdot C_i^k\times f(i-k)\times 2^{(i-k)} \end{aligned} \]
即得递推式。如果要求连通仿照无向图连通的方法，用任意减去不连通即可。
C - Amusement Park
https://codeforces.com/problemset/problem/1193/A
先考虑计算方案数。枚举 \(1\) 所在子集，那么有 \(f(S)=\sum\limits_{T\in S} (-1)^{|T|+1}\cdot f(S - T)\)。相较于一般的 DAG 计数，因为每条边取不取是固定的，所以没有了 \(2\) 的次幂的系数；同时因为直接枚举子集，所以没有了组合系数。
注意此处 \(T\) 可构成一轮新的入度为 \(0\) 的点集当且仅当 \(T\) 之内没有连边，即 \(T\) 为独立集。
算出方案数后如何算答案呢？发现对于一种合法的方案，把里面所有的边反向一定唯一对应另一种合法方案，两种方案取反边数相加为 \(m\)；那么给所有方案除以 \(2\)，再乘上 \(m\) 就能得到答案。
复杂度 \(O(3^n)\)。需要提前把每个点集是否独立预处理下来。
#include <bits/stdc++.h>
const int mod = 998244353, inv2 = (mod + 1) >> 1;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> g(n + 1);
for (int i = 1, x, y; i <= m; ++i) {
std::cin >> x >> y;
g[x] |= (1 << (y - 1));
g[y] |= (1 << (x - 1));
}
auto check = [&](int s) {
for (int i = 1; i <= n; ++i)
if ((s >> (i - 1)) & 1)
if (s & g[i])
return false;
return true;
};
int siz = 1 << n;
std::vector<int> tag(siz);
for (int i = 0; i < siz; ++i)
tag[i] = check(i);
std::vector<long long> f(siz);
f[0] = 1ll;
for (int i = 1; i < siz; ++i)
for (int j = i; j; j = (j - 1) & i)
if (tag[j])
(f[i] += ((__builtin_popcount(j) & 1) ? 1 : mod - 1) * f[i ^ j]) %= mod;
std::cout << f[siz - 1] * inv2 % mod * m % mod << '\n';
return 0;
}D - Balance Scale
https://atcoder.jp/contests/abc306/tasks/abc306_h
可以发现，如果将被 = 连起来的点缩起来，就可以转化成上一个问题。但枚举被缩的点集显然是不能通过的，这里介绍一种方法。
不把缩点放在开头。在上一题中的 DP 式子 \(f(S)=\sum\limits_{T\in S} (-1)^{|T|+1}\cdot f(S - T)\) 中，考虑和我们最终的答案有什么差异：
- 在现在的问题中，有的边是可以不选的！考虑这会给容斥带来怎样的影响。
首先应该知道一件事情：你决定把一部分点缩到一起，当且仅当它们全部由 = 连接。要让一些边加入 DP，也就是让它们不是 =，当且仅当它们成为连通块的『割』——把连通块分成多个连通块。这种情况显然已经由另一条路径转移过了。也就是说，就用这个式子可以得到所有答案。 1. 另一个问题，在上一题中，我们可以轻易地判断 \(T\) 是否为独立集；但在本问中，不是独立集的点集也可能缩点成为独立集。
发现有一种唯一方法，就是使 \(T\) 中位于同一连通块的点缩到一起；所以应该将 \(-1\) 的次数替换为 \(T\) 所在连通块个数 \(+1\)。
注意这里说的连通块是 \(T\) 的导出子图中的连通块。
这也启示我们不要把缩点和图的连通性等等关联得太死，需要把点等价的场景都可能用到缩点。
#include <bits/stdc++.h>
const int mod = 998244353, inv2 = (mod + 1) >> 1;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> fa(n + 1);
std::function<int(int)> find = [&](int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
};
auto merge = [&](int x, int y) {
fa[find(x)] = find(y);
return;
};
std::vector<std::vector<int> > g(n + 1);
for (int x, y; m--; ) {
std::cin >> x >> y;
g[x].push_back(y), g[y].push_back(x);
}
int siz = 1 << n;
std::vector<int> cnt(siz);
for (int i = 0; i < siz; ++i) {
std::iota(fa.begin(), fa.end(), 0);
std::vector<int> tag(n + 1);
for (int j = 1; j <= n; ++j)
if ((i >> (j - 1)) & 1)
for (auto k : g[j])
if ((i >> (k - 1)) & 1)
merge(k, j);
for (int j = 1; j <= n; ++j)
if ((i >> (j - 1)) & 1)
cnt[i] += (fa[j] == j);
}
std::vector<long long> f(siz);
f[0] = 1ll;
for (int i = 1; i < siz; ++i)
for (int j = i; j; j = (j - 1) & i)
if (cnt[j])
(f[i] += ((cnt[j] & 1) ? 1 : mod - 1) * f[i ^ j]) %= mod;
std::cout << f[siz - 1] << '\n';
return 0;
}E - 主旋律
https://www.luogu.com.cn/problem/P11714
即，给定一个有向图，问边集有多少个子集是强连通的。
再次涉及到了连通性问题，但在这里需要结合 SCC 缩点来考虑。容易发现强连通即缩出来是一个点；故需要关注缩出来的点数。
令 \(f(S)\) 表示 \(S\) 的导出子图内合法边子集的数量，\(g(S)\) 表示 \(S\) 的导出子图中非法边子集的数量；\(h(S,k)\) 表示 \(S\) 的导出子图中边的子集缩出来有 \(k\) 个点的数量， 令 \(E(S_1, S_2)\) 表示从 \(S_1\) 指向 \(S_2\) 的边数，则：
\[ f(S) = 2^{E(S,S)}-g(S)\\ g(S)=\sum_{T \subseteq S}2^{E(T, S - T)}\cdot 2^{E(T, T)}\cdot \sum_{k=1+[T=\varnothing]} (-1)^{k+1}\cdot h(S - T, k)\\ h(S, k) = \sum_{T\subset S} f(T) \cdot h(S - T, k-1) \]
注意为什么要用一个 \(h\) 来转移 \(g\) 呢？我们发现 \(-1\) 的次数和缩出来的点数是有关的，而光凭 \(g\) 无法表示点数信息，所以需要用 \(h\) 来搭个桥。
直接 DP，复杂度 \(O(n\cdot 3^n)\)。