题解|[HAOI2009]逆序对数列

这一题的题面，告诉我们是要求逆序对数为k的数列。

但是， 恐怖的数据范围说明了一切

n<=1000 k<=1000

这么大的数据，对于求逆序对的任何方法都是会TLE的

既然按照题面的说法不行，我们就在我们的知识范围内搜索：

图论？数论？dp？

(实际上并不是这么简单，要多做题才能理解这其中的套路)

没错！就是dp！

在dp中，有一种类型是专门用来计算符合每种规则的dp——计数dp

接下来，就是

设置状态

按照一贯的套路，求什么设什么

我们设f[i][j]为在长度为i的所有排列（全排列）中，逆序对数为j的个数

那么，如果我们想往一个长度为i的数列中加入一个数，使之成为长度为i+1的数列时，会多产生是多少呢？

我们设k表示这次更新会导致增加多少逆序对数

那么dp方程就是

f[i][j]=sigma(f[i-1][j-k])(k=0...min(i-1,j))

这个方程的复杂度很显然是通过不了题目的，所以我们还要进一步优化

我们发现，k是从0一直到一个固定的值的，所以我们可以考虑用前缀和来优化

#include<cstdio>
const long long mod=10000;
long long n,k,sum,f[1010][1010];
int main()
{
    scanf("%lld %lld",&n,&k);
    f[1][0]=1;
    for(long long i=2;i<=n;i++)
    {
        sum=0; //前缀和优化
        for(long long j=0;j<=k;j++)
        {
            sum+=f[i-1][j];
            sum=(sum%mod+mod)%mod; 
            f[i][j]=sum;
            if(j>=i-1)
                sum-=f[i-1][j-i+1],sum=(sum%mod+mod)%mod; }//这里注意要加上模数，不然会产生负数
    }
    printf("%lld\n",f[n][k]);
}