【ABC327G 题解 合卷后闲梦屏边雨细风斜飞去枝上鹊】兵戈声依稀吹远倒卷入重帘三鼓前城旗掩近昏的夜谁衣衫却白得那样惹眼像露晞前明明欲曙的天

· · 题解

赛时想到大致思路，但同一个图存在不同染色方式的情况没有处理好，导致最后两个样例过不去。

答案为 n 个点 m 条边（可能有重边）代标号二分图个数乘以 2^m，因为每条边可以有两种方向。

设 G_{n,m} 表示 n 个点、m 条边简单二分图的个数，染色方式不同算多种，枚举左边点的个数 i，则最多有 i(n-i) 条边，所以

G_{n,m}=\sum_{i=0}^nC_n^iC_{i(n-i)}^m

设 F_{n,m} 表示 n 个点、m 条边简单连通二分图的个数，染色方式不同算多种（显然有且只有两种染色方式），考虑容斥，总方案减去不合法方案，可以枚举编号为 1 的点所在连通块大小及边数，则

F_{n,m}=G_{n,m}-\sum_{i,j}C_{n-1}^{i-1}F_{i,j}G_{n-i,m-j}

边界为 F_{1,0}=1。

设 H_{n,m} 表示 n 个点、m 条边简单二分图的个数，染色方式不同算一种，则枚举 1 所在连通块的大小及边数转移，由于每种连通二分图在 F 中被计算了两次，需要除以 2，所以

H_{n,m}=\dfrac{\sum_{i,j}C_{n-1}^{i-1}F_{i,j}H_{n-i,m-j}}{2}

边界为 H_{0,0}=1。

最后枚举去重后的边数 m'，则对答案的贡献为 H_{n,m'} 乘以长度为 m、不同元素个数为 m' 的序列数量，即 m 个小球装进 m' 个盒子里没有空盒的方案数，根据容斥原理，枚举空盒数量 i，所以这个问题的答案为

\sum_{i=0}^{m'-1}(-1)^iC_{m'}^i(m'-i)^m 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 35, M = 230, P = 998244353, INV2 = (P + 1) / 2;

int n, m;
LL c[M][M], g[N][M], f[N][M], h[N][M];

inline LL ksm(LL a, LL n)
{
    LL res = 1;
    while(n)
    {
        if(n & 1) res = res * a % P;
        a = a * a % P;
        n >>= 1;
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i < M; i ++ )
    {
        c[i][0] = 1;
        for(int j = 1; j <= i; j ++ ) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
    }

    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= n; j ++ )
            for(int k = 0; k <= j * (i - j); k ++ )
                g[i][k] = (g[i][k] + c[i][j] * c[j * (i - j)][k]) % P;

    f[1][0] = 2;
    for(int i = 2; i <= n; i ++ )
        for(int j = i - 1; j <= i * i / 4; j ++ )
        {
            f[i][j] = g[i][j];
            for(int k = 1; k <= i; k ++ )
                for(int l = k - 1; l <= min(k * k / 4, j); l ++ )
                    f[i][j] = (f[i][j] - c[i - 1][k - 1] * f[k][l] % P * g[i - k][j - l] % P + P) % P;
        }

    h[0][0] = 1;
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= i * i / 4; j ++ )
            for(int k = 1; k <= i; k ++ )
                for(int l = k - 1; l <= min(k * k / 4, j); l ++ )
                    h[i][j] = (h[i][j] + c[i - 1][k - 1] * h[i - k][j - l] % P * f[k][l] % P * INV2) % P;

    LL res = 0;
    for(int i = 1; i <= n * n / 4; i ++ )
        for(int j = 0, x = 1; j < i; j ++ , x = -x)
            res = (res + h[n][i] * c[i][j] % P * ksm(i - j, m) % P * x + P) % P;

    printf("%lld\n", res * ksm(2, m) % P);
    return 0;
}