526互联

CF1542E1 Abnormal Permutation Pairs (easy version) 题解

发布时间 2023-09-16 11:10:50作者: 霜木_Atomic

CF1542E1 Abnormal Permutation Pairs (easy version) 题解

不会 Hard version

对于第一个限制字典序，我们可以考虑枚举前 \(i\) 位相同，然后考虑后 \(n-i\) 位。我们只需要保证 \(p_{i+1} < q_{i+1}\) 即可。

我们设 \(len = n - i\)。由于前 \(i\) 位完全相同，所以前 \(i\) 位内部的逆序对个数以及前 \(i\) 位与后 \(len\) 位之间产生的逆序对个数也是相同的，因此对于第二个条件，我们只需要满足 \(p\) 后 \(len\) 位的逆序对个数严格大于 \(q\) 的后 \(len\) 位的即可。

因为逆序对仅与相对大小有关，所以后 \(len\) 位可以抽象成一个 \(1\) 到 \(len\) 的排列。我们设 \(f_{len, j, k}\) 表示长度为 \(len\) 的排列，第一位是 \(j\)，有 \(k\) 个逆序对的方案数。则长度每增加一位，只用考虑新加入的 \(len\) 作为开头以及其他数作为开头的转移。有：

\[f_{len, len, k} = \sum_{j = 1}^{len-1} f_{len-1, j, k-(len-1)} \\ f_{len, j, k} = \sum_{t = 0}^{len-2} f_{len-1, j, k-t} (1 \leq j<len) \]

对于第一种转移，我们只需把上一层所有数作为开头的方案加起来；对于第二种转移，我们考虑 \(len\) 插入到除了开头以外的其他位置产生的新的逆序对即可。

其中第二个转移是 \(O(n^5)\) 的，我们发现枚举的 \(t\) 是一个区间内的答案，所以可以前缀和优化可以到 \(O(n^4)\)。

然后我们来考虑统计答案。我们设逆序对个数上界 \(mx = \frac{len \times (len-1)}{2}\)，\(sp\)、\(sq\) 分别为 \(p\) 和 \(q\) 中后 \(len\) 位的逆序对个数，一个朴素的答案式子如下：

\[\sum_{len = 1}^{n} {n \choose len} (n-len)! \sum_{j = 1}^{len} \sum_{sp = 1}^{mx} \sum_{k = j+1}^{len} \sum_{sq = 0}^{sp-1} f_{len, j, sp} \times f_{len, k, sq} \]

我们从 \(n\) 中选取 \(len\) 个数作为后缀，则剩下的 \(n-len\) 个数做前缀。前缀要求完全相同，但可以随意排列顺序。后半部分就是通过枚举来满足第一和第二个限制。

显然是一个 \(O(n^7)\) 的式子。我们调整一下这个式子：

\[\sum_{len = 1}^{n} {n \choose len} (n-len)! \sum_{j = 1}^{len} \sum_{sp = 1}^{mx} f_{len, j, sp} \times (\sum_{k = j+1}^{len} \sum_{sq = 0}^{sp-1} f_{len, k, sq}) \]

会发现后半部分是个矩形内的和，可以用二维前缀和优化到 \(O(1)\) 求出。前半部分枚举是 \(O(n^4)\) 的。

简单版就做完了，复杂度 \(O(n^4)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 54;
int mod;

void add(int &a, int b) {
	a = (a+b)%mod;
}
int f[N][N][N*N];
int n;
int fac[N];
int sum1[N][N][N*N];//第一个前缀和（可以滚动数组优化）
int sum2[N][N][N*N];//第二个前缀和（也可以滚动数组）
int C[N][N];

void prework() {
	fac[0] = 1;
	for(int i = 1; i<=n; ++i) {
		fac[i] = 1ll*fac[i-1]*i%mod;
	}
	C[0][0] = 1;
	for(int i = 1; i<=n; ++i) {
		C[i][0] = 1;
		for(int j = 1; j<=i; ++j) {
			C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
		}
	}//预处理阶乘和组合数
}
int main() {
	scanf("%d%d", &n, &mod);
	prework();
	f[1][1][0] = 1;
	for(int i = 2; i<=n; ++i) {
		for(int j = 1; j<i; ++j) {
			for(int k = i-1; k<=(i*(i-1)/2); ++k) {
				add(f[i][i][k], f[i-1][j][k-(i-1)]);
			}	
		}//新加入一个最大的数，让它作为开头

		for(int j = 1; j<i; ++j) {
			sum1[i-1][j][0] = f[i-1][j][0];
			for(int o = 1; o<=(i*(i-1)/2); ++o) {
				sum1[i-1][j][o] = f[i-1][j][o];
				add(sum1[i-1][j][o], sum1[i-1][j][o-1]);
			}//计算需要的前缀和
			for(int o = 0; o<=(i*(i-1)/2); ++o) {
				if(o > i-2) {
					add(f[i][j][o], (sum1[i-1][j][o] - sum1[i-1][j][o-(i-2)-1])%mod);
					if(f[i][j][o] < 0) f[i][j][o]+=mod;
				} else f[i][j][o] = sum1[i-1][j][o];
			}
		}//对于其他数作为开头的情况
	}
	int ans = 0;
	for(int i = 0; i<n-1; ++i) {
		int ret = 1ll*fac[i]*C[n][i]%mod;
		int len = n-i;
		int sum = 0;
		for(int j = 1; j<=len; ++j) {
			sum2[len][j][0] = f[len][j][0];
			add(sum2[len][j][0], sum2[len][j-1][0]);
			for(int k = 1; k<=(len*(len-1)/2); ++k){
				sum2[len][j][k] = f[len][j][k];
				add(sum2[len][j][k], (1ll * sum2[len][j][k-1] + 1ll * sum2[len][j-1][k] + 1ll * mod - 1ll*sum2[len][j-1][k-1])%mod);
			}
		}//预处理二维前缀和。

		for(int j = 1; j<=len; ++j) {
			for(int oa = 1; oa<=(len*(len-1)/2) ;++oa) {
				add(sum, 1ll*f[len][j][oa] * (1ll*sum2[len][len][oa-1] - sum2[len][j][oa-1])%mod);
			}
		}
		add(ans, 1ll*ret*sum%mod);
	}
	if(ans<0) ans+=mod;
	printf("%d\n", ans);
	return 0;
}