题解：AT_abc282_g [ABC282G] Similar Permutation

算是一种插入 DP 吧。

先考虑一维版本 AT_dp_t。我们设

f_{i,j}

表示填完前

i

个数，末尾的数是填的数中第几小的。转移时枚举第

i+1

位置放的数是前

i+1

第几小就行。关于正确性，我们将转移路径提取出来，每条可还原出一个不重的排列。

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

CPP

/*

		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;
}

题解：AT_abc282_g [ABC282G] Similar Permutation

文章操作

相关推荐

评论

题解：AT_abc282_g [ABC282G] Similar Permutation