逆序对方案数问题题解

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

朴素解法（70分）

枚举前 ( i-1 ) 个数产生的逆序对个数 ( k )（( k \in [0,j] )），状态转移方程为：
( f_{i,j} = f_{i,j} + f_{i-1,k} )
需满足 ( j - k \leq i - 1 )（即当前第 ( i ) 个数产生的逆序对个数不超过 ( i-1 )）。

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

优化到80分

由 ( j - k \leq i - 1 ) 推出 ( k \geq j - i + 1 )，但 ( k \geq 0 )，故 ( k \in [\max(0, j - i + 1), j] )。

#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)优化（前缀和优化）

通过前缀和数组减少重复计算，时间复杂度优化至 ( 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) ) 的算法，留给同学们后续探索。

设 $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)$ 的算法，留给同学们以后探索。