专栏文章

题解：AT_abc282_g [ABC282G] Similar Permutation

bbelot
AT_abc282_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqce8rj
此快照首次捕获于
2025/12/04 02:30
3 个月前
此快照最后确认于
2025/12/04 02:30
3 个月前
查看原文

Similar Permutation

观察题面，这是一道有关排列计数的问题。而对于排列问题，可以按照位置或值的具体值或相对值来 dp。而此题需要知道相邻位置两项的大小关系，则可以对每一个位置依次考虑其值在序列中的排名，即其相对的值。假设当前 dp 到位置 ii，观察整个排列中的位置 [1,i][1, i] 的部分离散化后的结果，就是一个 [1,i][1, i] 的排列，而离散化后的值也就是其原先从小到大的排名。此时从排列 [1,i−1][1, i-1]（相对位置，即离散化后的）转移过来。通过加入位置 ii 的数，把 [1,i−1][1, i-1] 的排列扩充到 [1,i][1, i]。按照大小顺序，把位置 ii 的数插在排列 [1,i−1][1, i-1] 的 ii 个空隙中的任意一个。此时，如果事先记录下了位置 i−1i-1 的数在排列 [1,i−1][1, i-1] 的相对位置，就容易知道两者的大小关系。而题中问了两个排列，则可以记录两者的相对位置。设 dpi,j,k,ldp_{i, j, k, l} 表示做到位置 ii，aia_i 在 [1,i][1, i] 的相对位置为 jj，bib_i 在 [1,i][1, i] 的相对位置为 kk，相似度为 ll 的方案数。则有转移 dpi,j,k,l=∑1≤j′<j,1≤k′<kdpi−1,j′,k′,l−1+∑1≤j′<j,k≤k′≤idpi−1,j′,k′,l+∑j≤j′≤i,1≤k′<kdpi−1,j′,k′,l+∑j≤j′≤i,k≤k′≤idpi−1,j′,k′,l−1dp_{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(n3k)O(n^3k)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...