本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-01-16 09:22:53

题目分析

设$f[i][j]$为用了前i个数产生j个逆序对的方案数。

$ f[i][j]=\sum_{j-i+1}^k f[i-1][k] $ 这是一段连续的数值，可以用区间和优化。

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
int n,k;
const int p=10000;
int f[2000][2000],s[2000][2000];
int main() {
    scanf("%d%d",&n,&k);
    f[1][0]=1;
    for(int i=0;i<=k;i++)s[1][i]=1;
    for(int i=2;i<=n;i++){
	
        for(int j=0;j<=k;j++) {
            if(j>=i)f[i][j]=(s[i-1][j]-s[i-1][j-i])%p;
            else f[i][j]=s[i-1][j];
       		if(j>=1)s[i][j]=(s[i][j-1]+f[i][j])%p;
       		else s[i][j]=f[i][j];
        }
      
   }

    printf("%d\n",(f[n][k]+p)%p);
    return 0;
}

滚动数组优化

本题的第$i$行只与$i-1$行相关。

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
int n,k;
const int p=10000;
int f[2][2000],s[2][2000];
int main() {
    scanf("%d%d",&n,&k);
    f[1][0]=1;
    for(int i=0;i<=k;i++)s[1][i]=1;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=k;j++) {
            if(j>=i)f[i&1][j]=(s[(i-1)&1][j]-s[(i-1)&1][j-i])%p;
            else f[i&1][j]=s[(i-1)&1][j];
       		if(j>=1)s[i&1][j]=(s[i&1][j-1]+f[i&1][j])%p;
       		else s[i&1][j]=f[i&1][j];
         
        }
      
	}

    printf("%d\n",(f[n&1][k]+p)%p);
    return 0;
}