题解：AT_abc327_g [ABC327G] Many Good Tuple Problems

· · 题解

设 dp_{i,j,k} 表示 i 个点，j 条不重的边，由 k 个连通二分图构成的图的数量，其中点有编号，边不区分顺序。

对于 k\ge 2 部分的转移，枚举 1 号点所在的连通块的边数和点数，有

dp_{i,j,k}=\sum\limits_{x,y}\binom{i-1}{x-1}dp_{x,y,1}dp_{i-x,j-y,k-1}

对于 k=1，考虑用总数减去 k\ge 2 的部分。求总数只需要枚举左部点的数量，有

dp_{i,j,1}=\dfrac{\sum\limits_{x=1}^{i-1}\binom{i}{x}\binom{x(i-x)}{j}-\sum_{k=2}^i2^kdp_{i,j,k}}{2}

算答案时枚举本质不同的边的数量，容斥一下即可。

时间复杂度 O(n^7)，但常数很小，可以通过！

::::info[代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 35, mod = 998244353;
int n, m;
int dp[maxn][maxn * maxn][maxn];
int c[maxn * maxn][maxn * maxn];
int ans;
int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}
void init(int n) {
    for (int i = 0; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m; init(n * n);
    dp[1][0][1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= i * (i - 1) / 2; j++) {
            for (int k = 2; k <= i; k++)
                for (int x = 1; x < i; x++)
                    for (int y = 0; y <= j; y++)
                        dp[i][j][k] = (dp[i][j][k] + dp[x][y][1] * dp[i - x][j - y][k - 1] % mod * c[i - 1][x - 1]) % mod;
            for (int x = 1; x < i; x++) dp[i][j][1] = (dp[i][j][1] + c[x * (i - x)][j] * c[i][x]) % mod;
            for (int x = 2; x <= i; x++) dp[i][j][1] = (dp[i][j][1] - dp[i][j][x] * power(2, x)) % mod;
            dp[i][j][1] = (mod + 1) / 2 * dp[i][j][1] % mod;
            if (i - j > 1) dp[i][j][1] = 0;
        }
    for (int i = 1; i <= min(m, n * (n - 1) / 2); i++) {
        int sum = 0;
        for (int j = 1; j <= n; j++) sum = (sum + dp[n][i][j]) % mod;
        for (int j = 0; j <= i; j++) {
            int s = c[i][j] * power(2 * j, m) % mod * sum % mod;
            if ((i - j) & 1) ans = (ans - s) % mod;
            else ans = (ans + s) % mod;
        }
    }
    cout << (ans + mod) % mod << '\n';
    return 0;
}

::::