题目描述

对于一个数列{ai}，如果有i<j且ai>aj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的

数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？

输入

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

输出

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

样例输入

4 1

样例输出

3

---

题解

dp傻*题

设f[i][j]表示1~i组成逆序对个数为j的数列的方案数，那么考虑第i个元素，它对逆序对个数可能产生0~i-1的贡献。

所以有f[i][j]=∑f[i-1][j-k]，0≤k<i。

然后用一个前缀和来优化即可。注意点边界什么的就行。

#include 
     
       #include 
      
        #define mod 10000 using namespace std; int f[1010][1010] , sum[1010][1010]; int main() {     int n , k , i , j;     scanf("%d%d" , &n , &k);     f[0][1] = sum[0][1] = 1;     for(i = 1 ; i <= n ; i ++ )     {         for(j = 1 ; j <= k + 1 && j <= i * (i - 1) / 2 + 1 ; j ++ ) f[i][j] = (sum[i - 1][j] - sum[i - 1][max(0 , j - i)] + mod) % mod;         for(j = 1 ; j <= k + 1 ; j ++ ) sum[i][j] = (sum[i][j - 1] + f[i][j]) % mod;     }     printf("%d\n" , f[n][k + 1]);     return 0; }