求N排列中逆序数对为K对的个数。
需要一个小技巧。一个形为{2，1，5，3，4}的5-排列，可以转化为一个{0，1，0，1，1}的排列。这里每个元素A
i表示i前逆序数的对数。易证明两者一一对应。
这样就把问题转化为求
åAi=K，Ai<=i的排列个数。设F（i，j）表示前i个数之和达到j的排列个数，DP打表即得解。
1
#include <cstdio>
2#include <string>
3
4const int MAXN = 20;
5
6int m[21][201][MAXN], N, K;
7
8void add ( int x1, int m1, int x2, int m2 )
9
{
10
int i;
11 for ( i = 0; i < MAXN; i ++ )
12
{
13 m[x1][m1][i] += m[x2][m2][i];
14
}
15 int c = 0;
16 for ( i = 0; i < MAXN; i ++ )
17 {
18 int t = c + m[x1][m1][i];
19 c = t / 10;
20 m[x1][m1][i] = t % 10;
21 }
22
}
23
24void print ( int x1, int m1 )
25{
26 //printf ( "$%d\n", m[x1][m1][1] );
27 int i;
28 for ( i = MAXN - 1; m[x1][m1][i] == 0 && i >= 0; i -- )
29 ;
30 if ( i == -1 )
31 {
32 printf ( "0" );
33 }
34 else
35 {
36 for ( ; i >= 0; i -- )
37 {
38 printf ( "%d", m[x1][m1][i] );
39 }
40 }
41}
42
43void dp ()
44{
45 memset ( m, 0, sizeof ( m ) );
46 int i, j, k;
47 m[0][0][0] = 1;
48 for ( i = 1; i < 20; i ++ )
49 {
50 for ( j = 0; j < 200; j ++ )
51 {
52 for ( k = 0; k <= i && j - k >= 0; k ++ )
53 {
54 add ( i, j, i - 1, j - k );
55 }
56 }
57 }
58 //pt ();
59}
60
61int main ()
62{
63 //freopen ( "in.txt", "r", stdin );
64 dp ();
65 while ( scanf ( "%d %d", &N, &K ) )
66 {
67 if ( N == 0 && K == 0 )
68 {
69 break;
70 }
71 print ( N - 1, K );
72 printf ( "\n" );
73 }
74 return 0;
75}