题解：AT_abc282_g [ABC282G] Similar Permutation

belot · 2025-02-04 17:07:50 · 题解

Similar Permutation

观察题面，这是一道有关排列计数的问题。而对于排列问题，可以按照位置或值的具体值或相对值来 dp。而此题需要知道相邻位置两项的大小关系，则可以对每一个位置依次考虑其值在序列中的排名，即其相对的值。假设当前 dp 到位置 i，观察整个排列中的位置 [1, i] 的部分离散化后的结果，就是一个 [1, i] 的排列，而离散化后的值也就是其原先从小到大的排名。此时从排列 [1, i-1]（相对位置，即离散化后的）转移过来。通过加入位置 i 的数，把 [1, i-1] 的排列扩充到 [1, i]。按照大小顺序，把位置 i 的数插在排列 [1, i-1] 的 i 个空隙中的任意一个。此时，如果事先记录下了位置 i-1 的数在排列 [1, i-1] 的相对位置，就容易知道两者的大小关系。而题中问了两个排列，则可以记录两者的相对位置。设 dp_{i, j, k, l} 表示做到位置 i，a_i 在 [1, i] 的相对位置为 j，b_i 在 [1, i] 的相对位置为 k，相似度为 l 的方案数。则有转移 dp_{i, j, k, l}=\sum_{1\leq j'<j, 1\leq k'<k} dp_{i-1, j', k', l-1}+\sum_{1\leq j'<j, k\leq k'\leq i} dp_{i-1, j', k ', l}+\sum_{j\leq j'\leq i, 1\leq k'<k} dp_{i-1, j', k', l}+\sum_{j\leq j'\leq i, k\leq k'\leq i} dp_{i-1, j', k', l-1}。这个式子再使用前缀和优化即可。时间复杂度 O(n^3k)。

#define L(i, j, k) for (int i=(j); i<=(k); ++i)
const int N=110;
int n, kn, mod, dp[N][N][N][N];
signed main() {
    rd(n, kn, mod);
    dp[1][1][1][0]=1;
    L(i, 2, n) {
        L(j, 1, i) L(k, 1, i) L(l, 0, i-1) {
            if (l) dp[i][j][k][l]=((ll)dp[i][j][k][l]+dp[i-1][j-1][k-1][l-1]+dp[i-1][i-1][i-1][l-1]-dp[i-1][j-1][i-1][l-1]-dp[i-1][i-1][k-1][l-1]+dp[i-1][j-1][k-1][l-1])%mod;
            dp[i][j][k][l]=((ll)dp[i][j][k][l]+dp[i-1][j-1][i-1][l]-dp[i-1][j-1][k-1][l]+dp[i-1][i-1][k-1][l]-dp[i-1][j-1][k-1][l])%mod;
        }
        L(j, 1, i) L(k, 1, i) L(l, 0, i-1) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i][j][k-1][l])%mod;
        L(j, 1, i) L(k, 1, i) L(l, 0, i-1) dp[i][j][k][l]=(dp[i][j][k][l]+dp[i][j-1][k][l])%mod;
    }
    printf("%d\n", (dp[n][n][n][kn]+mod)%mod);
    return 0;
}