P2513 [HAOI2009] 逆序对数列

wflengxuenong · 2025-01-16 09:22:53 · 个人记录

题目分析

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

这是一段连续的数值，可以用区间和优化。

参考代码

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