题解：AT_agc068_e [AGC068E] Sort and Match

· · 题解

小清新。

题意：给出一个 n\times n 的矩阵 A，定义一个值域为 [1,n] 长为 m 的序列 x，令其排序后的序列为 y，则 x 的权值为 \prod A_{x_i,y_i}，求对于 i=1\to n，所有合法的 x 且 x_1 = i 的序列权值之和。n,m\le 50。

做法：

首先考虑他是形如一个序列及其置换，所以我们考虑比如 y_i\to x_i 这样连一条边，显然这样会形成一个欧拉图，那么我们就考虑把这个图分成若干个欧拉回路，形成一个一一映射这样就方便我们的统计。

我们思考如果随意拉一个欧拉回路麻烦的点在哪里，发现就是对于相同的 y\to x，我们并不是很好确定我们走的是哪一个，所以我们考虑，我们给 y_i\to x_i 赋一个 i 的权，每次优先走权最大的没走过的边，这样对于一个图走法唯一，同时如果我们一个一个欧拉回路加回来，就一直往对应的位置加边即可，可以唯一还原一个图，这样就形成了一个双射。为了顺序，我们这里欧拉回路一定在整个路最小的边作为第一个进行遍历。

所以我们现在就只需要计算所有欧拉回路的权即可，我们枚举开始的位置是哪里，然后每次去拓展一条边即可，这个计算很简单。

然后最后还要做一次 dp 整合一下答案，直接就是对于长度 i 且最小值为 j 的情况的答案是多少这样统计即可。注意题目要求对于 x_1=1\to n 都要计算，那么我们就倒序做 dp，最后在 i=m 时记录即可，只需要在计算欧拉回路的时候记录一下 x_1 是多少即可，具体细节可以看代码。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 55 + 5, mod = 998244353;
int n, m, coef[maxn][maxn][maxn], s[maxn][maxn], ans[maxn], a[maxn][maxn];
int nw[maxn][maxn], dp[maxn][maxn];
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        memset(nw, 0, sizeof(nw));
        nw[1][i] = 1;
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k <= n; k++) {
                coef[i][j][k] = (coef[i][j][k] + nw[j][k] * a[k][i]) % mod;
                s[i][j] = (s[i][j] + nw[j][k] * a[k][i]) % mod;
                for (int t = i + 1; t <= n; t++)
                    nw[j + 1][t] = (nw[j + 1][t] + nw[j][k] * a[k][t]) % mod;
            //  cout << i << " " << j << " " << k << " " << nw[j][k] << endl;
            }
        //  cout << i << " " << j << " " << s[i][j] << endl;
        }
    }
    for (int i = 1; i <= n; i++)
        dp[m + 1][i] = 1;
    for (int i = m; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            if(i != 1) {
                for (int k = 1; i + k <= m + 1; k++)
                    dp[i][j] = (dp[i][j] + dp[i + k][j] * s[j][k]) % mod;
            }
            else {
                for (int k = 1; i + k <= m + 1; k++)
                    for (int t = j; t <= n; t++)
                        ans[t] = (ans[t] + dp[i + k][j] * coef[j][k][t]) % mod;
            }
        }
        for (int j = n; j >= 1; j--)
            dp[i][j] = (dp[i][j + 1] + dp[i][j]) % mod;
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}