http://user.qzone.qq.com/1304445713/blog/1351823901
现在我们来分析这个问题：
用 f(n, k) 表示 n 的全排列 的 k逆序对 的排列种数。并且对于不存在的排列，我们都设为0。
可知，n为任何值时，f(n, 0) = 1。那么，f(n, k) 是多少呢，我们来假设全排列的第一位。
当第一位是1时，因为 1 比任何数小，所以不会与后面的数构成逆序对，也就是说，
后面的 (n-1) 个数还要构成 k 个逆序对，所以数量是 f(n-1, k)。
当第一位是 2 时，会与后面的 1 构成一对逆序对，也就是说，
后面还要构成 k - 1 个逆序对，也就是 f(n-1, k-1)。
当第一位是 3 时，同理，3和后面的数构成 2 个逆序对，所以数量是 f(n-1, k-2)。
递推公式似乎得到了，但是，还要注意边界！
因为是 n 个数的全排，所以第一位不会大于 n ，那么最后一个被加上的数只是 f(n-1, k-n+1)，而不是 f(n-1,0)。
好了，至此，递推公式得出 f(n, k) = sigma{ f(n-1, i) } i = (k - n + 1) to (k - 1) //sigma是求和累加
还没结束！这个递推公式中含有一个循环，效率太低，我们还可以继续推导！
如果用了暴力程序打表，我们会发现一个规律，很多数据 f(n, k) = f(n-1, k) + f(n, k-1)
这是为什么呢？ 我们来分析 f(n, k-1) 是个什么东西：
根据我们已经得出的递推公式，可以知道，f(n, k-1) = sigma{ f(n-1, i) } i = (k - n) to (k - 2)
发现了！这个式子中，包含了我们求 f(n, k) 所需的大量元素，只是多了一个 f(n-1, k-n)！
所以，递推公式被化简，得到 f(n, k) = f(n-1, k) + f(n, k-1) - f(n-1, k-n)
此题的复杂度被降低为 O(n2)，可以秒杀了~
此题还有几个关于取模的细节需要注意：
首先是求余定理， (a + b) % m = ((a % m) + (b % m)) % m
所以此题直接在推导过程中每次取模就行。
但是需要注意的是，因为取过模，f(n-1, k) + f(n, k-1) 可能比 f(n-1, k-n) 更小！
所以要判断，出现负数时，把模加回去！
代码如下：(如需复制，用UltraEdit等编辑器，alt+选择前三列，可以删除行号)
02
03 using namespace std;
04
05 int t, n, k;
06 int ans[1005][1005] = {};
07
08 void pro();
09
10 int main()
11 {
12 scanf("%d", &t);
13
14 pro();
15 //预先求出整个答案表
16
17 while (t--)
18 {
19 scanf("%d%d", &n, &k);
20 printf("%d\n", ans[n][k]);
21 }
22
23 return 0;
24 }
25
26 void pro()
27 {
28 for (int i = 1; i <= 1000; i++)
29 ans[i][0] = 1;
30
31 for (int i = 2; i <= 1000; i++)
32 for (int j = 1; j <= 1000; j++)
33 {
34 ans[i][j] = (ans[i-1][j] + ans[i][j-1]) % 10000;
35 if (j >= i) //P党可以把数组下标开负数，C党就老老实实判断吧
36 {
37 ans[i][j] -= ans[i-1][j-i];
38 if (ans[i][j] < 0)
39 ans[i][j] += 10000;
40 }
41 }
42 }