题解：AT_abc282_g [ABC282G] Similar Permutation

FS_NEO · 2025-11-17 23:22:03 · 题解

算是一种插入 DP 吧。

先考虑一维版本 AT_dp_t。我们设 f_{i,j} 表示填完前 i 个数，末尾的数是填的数中第几小的。转移时枚举第 i+1 位置放的数是前 i+1 第几小就行。关于正确性，我们将转移路径提取出来，每条可还原出一个不重的排列。

本题是二维版本，将前缀和优化改成二维前缀和优化就行了。

/*

        2025.11.17

  * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
const int MAXN=105;
int n,k,ans,f[MAXN][MAXN][MAXN][MAXN],mod,s[MAXN][MAXN][MAXN][MAXN];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin>>n>>k>>mod;
    f[1][0][1][1]=1;
    for(int i=2;i<=n;i++){
        for(int _=0;_<=i;_++){
            for(int j=1;j<i;j++){
                for(int k=1;k<i;k++)s[i-1][_][j][k]=(s[i-1][_][j][k-1]+f[i-1][_][j][k])%mod;
                for(int k=1;k<i;k++)s[i-1][_][j][k]=(s[i-1][_][j][k]+s[i-1][_][j-1][k])%mod;
            }
            for(int j=1;j<=i;j++){
                for(int k=1;k<=i;k++){
                    //< <
                    f[i][_+1][j][k]=(f[i][_+1][j][k]+s[i-1][_][i-1][i-1]-s[i-1][_][i-1][k-1]-s[i-1][_][j-1][i-1]+s[i-1][_][j-1][k-1])%mod;
                    //< >
                    f[i][_][j][k]=(f[i][_][j][k]+s[i-1][_][i-1][k-1]-s[i-1][_][j-1][k-1])%mod;
                    //> <
                    f[i][_][j][k]=(f[i][_][j][k]+s[i-1][_][j-1][i-1]-s[i-1][_][j-1][k-1])%mod;
                    //> >
                    f[i][_+1][j][k]=(f[i][_+1][j][k]+s[i-1][_][j-1][k-1])%mod;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans=(ans+f[n][k][i][j])%mod;
    cout<<(ans+mod)%mod;
    return 0;
}