题解 [email protected]洛谷 | [email protected] 【PERMUT1 - Permutations】

本题是三倍经验 Link1 Link2,不知道为啥这几题难度评分不一样,区别只有多组数据和模数。

好了,下面进入正题。


题意简述:多组数据,给定 nn,求 1n1\sim n 的所有排列中逆序对个数恰有 kk 个的情况。

由于有多组数据,因此考虑预处理出所有情况后进行 O(1)O(1) 查询,虽然这题数据范围较小好像也不用。

怎么进行预处理呢?考虑进行动态规划。

设计状态 dpi,jdp_{i,j} 表示对于 1i1\sim i 的所有排列,恰有 jj 个逆序对的情况总数。

考虑如何进行转移。我们在 1i11\sim i-1 的一个排列,添加一个数 ii,此时我们可以使逆序对个数增加 1,2,,i11,2,\cdots,i-1 个。因此,我们可以得到转移方程:

dpi,j=k=0i1dpi1,jkdp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}

此时,根据我们状态的定义,dpn,kdp_{n,k} 即为所求。


这是我们注意到一个问题:这个转移是 O(n3)O(n^3) 的,无法通过上面两道双倍经验,因此需要优化。

看到我们最后一维要加的是一个区间内的 dpdp 值,容易想到通过维护前缀和来优化时间。我们采取循环中滚动求前缀和的方式。

代码中的前缀和开的是数组,也有只用一个变量的做法(其实并不难),因为我懒,这里就不写了。

另外,由于数量可能很大,需要开 long long。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1005;

ll T, n, m;
ll dp[N][N] = {{0}, {1}}, s[N];

void dpInit() {
	for(ll i=2;i<=1000;i++) {
		memset(s, 0, sizeof(s));
		for(ll j=0;j<=1000;j++) {
			s[j] = dp[i-1][j];
			if(j) s[j] += s[j-1];
			dp[i][j] = s[j];
			ll _ = j - i + 1;
			if(_ >= 0) s[j] -= dp[i-1][_];
		}
	}
}

int main() {
	dpInit();
	scanf("%lld", &T);
	while(T--) {
		scanf("%lld%lld", &n, &m);
		printf("%lld\n", dp[n][m]);
	}
	return 0;
}