【BZOJ 2431】【HAOI 2009】逆序对数列【DP+优化】

Description

对于一个数列{ai}，如果有i

Input

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

Output

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

Sample Input

4 1

Sample Output

3 样例说明： 下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4； 100%的数据 n<=1000，k<=1000

题解

f[i][j]表示到第i个数有j个逆序对，∴f[i][j]=sigma{f[i-1][j-k]) k∈[0,i) 但是这是O(n^3)的，所以我们观察式子，发现好像与前缀和有关，所以可以用前缀和优化一维，变成O(n^2)就可以了。 同时，通过i与i-1可以看出，我们还能使用滚动数组。

代码