[CF2145D] Inversion Value of a Permutation

题目

CF2145D。

思路

注意 inversion value 的定义，它是存在逆序对的 subsegment 的数量，并非逆序对的数量。

存在性的数数一般都不是很好做，我们可以看它的反面，那就是不存在逆序对的 subsegment 的数量，现在我们统计这种 $(l,r)$ 的数量。

不存在逆序对，那就是一段 $(l,r)$ 满足 $a_l<a_{l+1}<\cdots<a_r$。

很自然地，我们可以对每个满足要求的 $(l,r)$ 尽可能向左右延，直到不能延为止。

对于这样一个极大的 $(l,r)$，假设它的长度是 $L=r-l+1$，那么它对我们要统计的数量的贡献是 $\binom{L}{2}$。

显然，任何一个序列，都是一堆这种极大的 $(l,r)$ 拼在一起的。因为你无论如何都能把这个序列划分成若干个极大的首尾相接的 $(l,r)$，并且每一个极大的 $(l,r)$ 都是孤立的，即整个序列的贡献就是每一段的贡献之和。

因此，现在的问题就转化成了，我们需要构造一组 $L_1,L_2,\dots,L_k$ 满足 $\sum L_i=n$ 且 $\sum \binom{L_i}{2}=\binom{n}{2}-k$。

设 $dp_{i,j,k}$ 表示考虑 $L$ 的值为前 $i$ 个数，$\sum L=j$，$\sum\binom{L}{2}=k$ 是否存在，并且需要记录 $pre_{i,j,k}$ 表示当前状态从哪个状态转移过来。

转移的话，枚举 $l\ge 0$ 个 $i+1$，会有：

$$dp_{i+1,j+l(i+1),k+l\binom{i+1}{2}}\gets dp_{i,j,k}$$

最终构造只要从 $n-L+1,n-L+2,\dots,n$ 这样入手就行了。

实现

#include <bits/stdc++.h>
using namespace std;

const int N = 31;
bool dp[N][N][N*(N-1)/2];
struct Sol {
    int cur, j, k;
} pre[N][N][N*(N-1)/2];

void solve() {
    int n, tar;
    cin >> n >> tar;
    tar = n * (n-1) / 2 - tar;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= tar; k++) {
                dp[i][j][k] = 0;
                pre[i][j][k] = {-1, -1, -1};
            }
        }
    }
    dp[0][0][0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= tar; k++) {
                if (!dp[i][j][k]) continue;
                for (int l = 0; j+l*(i+1) <= n && k+l*(i+1)*i/2 <= tar; l++) {
                    dp[i+1][j+l*(i+1)][k+l*(i+1)*i/2] = true;
                    pre[i+1][j+l*(i+1)][k+l*(i+1)*i/2] = {l, j, k};
                }
            }
        }
    }

    int now = n;
    auto print = [&](int s){
        for (int i = now-s+1; i <= now; i++) {
            cout << i << ' ';
        }
        now -= s;
    };
    if (!dp[n][n][tar]) cout << "0\n";
    else {
        int i = n, j = n, k = tar;
        for (int i = n; i >= 1; i--) {
            Sol s = pre[i][j][k];
            j = s.j;
            k = s.k;
            for (int q = 1; q <= s.cur; q++) {
                print(i);
            }
        }
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}