[前缀和优化dp][HAOI 2009] 逆序对数列

题目描述

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

输入格式

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

输出格式

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

输入1 :

4 1

输出1 :

3

样例说明：

下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；

测试数据范围

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

题解

不妨设(dp[i][j])表示逆序对数为(j)的由(1sim i)构成的数列的数量。
设(L=maxleft(0,j-i+1 ight),R=minleft(frac{left(i-1 ight)left(i-2 ight)}{2},j ight))，
则(dpleft[i ight]left[j ight]=sum_{k=L}^{R}dpleft[i-1 ight]left[k ight])。
设(Sumleft[i ight]left[j ight]=sum_{j} d pleft[i ight]left[j ight])，
则(dpleft[i ight]left[j ight]=Sumleft[i-1 ight]left[R ight]-Sumleft[i-1 ight]left[L-1 ight])。
时间复杂度(O(nk))。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

const int MOD=10000;
int dp[1005][1005],Sum[1005][2];
int N,M;

int main(){
    scanf("%d%d",&N,&M);
    int sta=1;
    for(register int i=1;i<=N;++i){
        dp[i][0]=1;
        Sum[0][sta]=1;
        for(register int j=1;j<=min(M,i*(i-1)/2);++j){
            int L=max(0,j-i+1);
            int R=min((i-1)*(i-2)/2,j);
            if(L==0) dp[i][j]=Sum[R][sta^1]%MOD;
            else dp[i][j]=((Sum[R][sta^1]-Sum[L-1][sta^1])%MOD+MOD)%MOD;
            Sum[j][sta]=(Sum[j-1][sta]+dp[i][j])%MOD;
        }
        sta^=1;
    }
    printf("%d
",dp[N][M]%MOD);
    return 0;
}