Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

06/12
11:08
一般动规与递推

[bzoj 2431] [HAOI2009]逆序对数列

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行为两个整数nk

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4 1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

3

样例说明:
下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;
测试数据范围
30%的数据 n<=12
100%的数据 n<=1000,k<=1000

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

把i插入1~i-1的排列中,可能产生0~i-1个逆序对,所以f[i][j]=Σf[i-1][k] (j-i+1<=k<=j)

维护一个前缀和直接dp就行了

 

[bzoj 2431] [HAOI2009]逆序对数列