首先进行一个容斥，把连通块最大值 \(= K\) 变成 \(\le K\) 的方案数减去 \(\le K - 1\) 的方案数。
考虑 dp，设 \(f_{i, j}\) 表示当前用了 \(i\) 个点，\(j\) 条边。转移即枚举其中一个连通块的大小 \(k\)。为了不算重，我们强制让这个连通块包含点 \(1\)，类比状压中枚举包含 \(\text{lowbit}(S)\) 的子集。
- 如果这个连通块是环，那么给这个连通块标号 \(1 \sim k\) 的方案数为 \(\frac{(k - 1)!}{2}\)，从 \(f_{i - k, j - k}\) 转移。特别地，\(2\) 元环的方案数为 \(1\)。
- 如果这个连通块是链，那么方案数为 \(\frac{k!}{2}\)，从 \(f_{i - k, j - (k - 1)}\) 转移。
还要乘一个给这 \(k\) 个点选择标号的方案数。\(1\) 被确定一定要选，剩下 \(i - 1\) 个标号要选 \(k - 1\) 个，所以方案数就是 \(\binom{i - 1}{k - 1}\)。
时间复杂度 \(O(n^3)\)。
code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 310;
const ll mod = 1000000007;
const ll inv2 = (mod + 1) / 2;
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, K, 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;
}
}
ll f[maxn][maxn];
inline void upd(ll &x, ll y) {
((x += y) >= mod) && (x -= mod);
}
inline ll calc(ll K) {
if (!K) {
return 0;
}
mems(f, 0);
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
f[i][j] = f[i - 1][j];
for (int k = 2; k <= K && k <= i; ++k) {
if (k <= j && k > 2) {
upd(f[i][j], f[i - k][j - k] * C(i - 1, k - 1) % mod * fac[k - 1] % mod * inv2 % mod);
}
if (k <= j && k == 2) {
upd(f[i][j], f[i - k][j - k] * C(i - 1, k - 1) % mod);
}
if (k - 1 <= j) {
upd(f[i][j], f[i - k][j - (k - 1)] * C(i - 1, k - 1) % mod * fac[k] % mod * inv2 % mod);
}
}
}
}
return f[n][m];
}
void solve() {
scanf("%lld%lld%lld", &n, &m, &K);
if (n < m || n < K) {
puts("0");
return;
}
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;
}
printf("%lld\n", (calc(K) - calc(K - 1) + mod) % mod);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}