怎么连这种相对传统的计数也不会……
考虑换种方式描述强连通分量个数。考虑竞赛图缩点后存在一条极长的链,因此转化为把缩完点后的链劈成左右两个集合,使得左边集合不为空的方案数。
于是我们现在只要统计点集 \(A, B\) 数量,满足 \(A \ne \varnothing, A \cap B = \varnothing, A \cup B = [1, n]\) 且 \(A\) 中的边始终指向 \(B\)。
考虑 dp。设 \(f_{i, j, k}\) 为考虑了 \([1, i]\) 的点,\(|A| = j\),小连到大的边数为 \(k\) 的方案数。转移讨论 \(i + 1\) 分给 \(A\) 还是 \(B\) 即可,枚举对应集合中有多少 \(u \to i + 1\) 的点即可。
时间复杂度 \(O(n^5)\)。
code
// Problem: D - Sum of SCC
// Contest: AtCoder - AtCoder Regular Contest 163
// URL: https://atcoder.jp/contests/arc163/tasks/arc163_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 35;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, f[maxn][maxn][maxn * maxn], fac[maxn], ifac[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
inline void upd(ll &x, ll y) {
x += y;
(x >= mod) && (x -= mod);
}
void solve() {
scanf("%lld%lld", &n, &m);
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
f[0][0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 0; k <= m; ++k) {
if (!f[i][j][k]) {
continue;
}
for (int l = 0; l <= j; ++l) {
upd(f[i + 1][j + 1][k + l], f[i][j][k] * C(j, l) % mod);
}
for (int l = 0; l <= i - j; ++l) {
upd(f[i + 1][j][k + j + l], f[i][j][k] * C(i - j, l) % mod);
}
}
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + f[n][i][m]) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest 163 Sumatcoder regular contest 163 sum atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest 167 atcoder regular contest builder