Description

【题目描述】

对于一个数列 $\{a_i\}$，如果有 $i<j$ 且 $a_i>a_j$，那么我们称 $a_i$ 与 $a_j$ 为一对逆序对数。若对于任意一个由 $1 \sim n$ 自然数组成的数列，可以很容易求出有多少个逆序对数。那么逆序对数为 $k$ 的这样自然数数列到底有多少个？

【输入格式】

第一行为两个整数n，k。

【输出格式】

写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。

【样例输入 #1】

4 1

【样例输出 #1】

3

【样例说明：】

下列3个数列逆序对数都为1；

分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

【测试数据范围】

数据 by chenjunyuWC

100%的数据  n<=1000，k<=1000

Hint

设 $f_{i,j}$ 表示前 $i$ 个数构成 $j$ 个逆序对的方案数。

可以枚举前 $i-1$ 个数产生了 $k$ 个逆序对，显然有 $k \in [0,j]$。

状态转移方程：$f_{i,j}=f_{i,j}+f_{i-1,k}$。

不过要判断当前第 $i$ 个数产生的逆序对个数是否小于 $i-1$。

这是朴素 70 分代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
const int mod=10000;
int f[N][N];
int main(){
	int n,m;scanf("%d%d",&n,&m);
	f[1][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=j;k++)
				if(j-k<=i-1)
					f[i][j]=(f[i][j]+f[i-1][k])%mod;
	printf("%d",f[n][m]);
	return 0;
}

由 $j-k \le i-1$ 可以推出 $k \ge j-i+1$。

但是直接让 $k \in [j-i+1,j]$ 会有问题，因为 $j-i+1$ 有可能为负数。

$\therefore k \in [\max(0,j-i+1),j]$

这是 80 分的代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
const int mod=10000;
int f[N][N];
int main(){
	int n,m;scanf("%d%d",&n,&m);
	f[1][0]=1;
	for(int i=2;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=max(0,j-i+1);k<=j;k++)
				f[i][j]=(f[i][j]+f[i-1][k])%mod;
	printf("%d",f[n][m]);
	return 0;
}

上面两个代码时间复杂度：$O(nk^2)$。

我们发现 $f$ 数组的转移可以用前缀和优化。

时间复杂度：$O(nk)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
const int mod=10000;
int f[N][N],sum[N];
int main(){
	int n,m;scanf("%d%d",&n,&m);
	f[1][0]=1;
	for(int i=2;i<=n;i++){
		memset(sum,0,sizeof(sum));
		for(int j=0;j<=m;j++){
			sum[j]=(sum[j-1]+f[i-1][j])%mod;
			f[i][j]=sum[j];
			if(j-i+1>=0){
				f[i][j]=(sum[j]-sum[j-i]+mod)%mod;
			}
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

事实上本题还有 $O(n \ln n)$ 的算法，留给同学们以后探索。

Source

cjy