逆序排列
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。
1-n的全排列中，逆序数最小为0（正序），最大为n*(n-1) / 2（倒序）
给出2个数n和k，求1-n的全排列中，逆序数为k的排列有多少种？
例如：n = 4 k = 3。
1 2 3 4的排列中逆序为3的共有6个，分别是：
1 4 3 2
2 3 4 1
2 4 1 3
3 1 4 2
3 2 1 4
4 1 2 3
由于逆序排列的数量非常大，因此只需计算并输出该数 Mod 10^9 + 7的结果就可以了。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数n，k。中间用空格分隔。（2 <= n <= 1000, 0 <= k <= 20000)
Output
共T行，对应逆序排列的数量 Mod (10^9 + 7)
Input示例
1
4 3
Output示例
6
题意分析：
这道题，如果没有想到动态规划的话，很难想到其他的方法，动态规划的一个思想应该就是，下一个状态和上一个状态之间又怎样的联系，如果你找到了这个联系，然后通过分析整理，得到一个动态转移方程，那么你离AC这道题就不远了。这道题可以作为动态规划的一个典型例题，应为动态转移方程的推导过程很不错，话不多说，让我们来看看如何推导的吧!
推导过程：
首先，你要想到一个动态转移dp【i】【j】数组，并且确定好代表什么意思，
dp【i】【j】表示：1到i这i个数字的全排列当中，逆序数为j的排列数，
这个数组的含义对后面的过程意思我觉得挺大的，要不都无从下手，
下面开始分析：上下两个状态之间的联系
dp【n】【k】=Σdp【n-1】【k-i】（0<=i<=n-1）
在0到n-1数字当中再加入一个数字n，该数字n有n-1个n个位置可以放，放这n个位置的时候还会额外的增加排列的逆序数，当放在首位置（i = 0），由于后面的都比数字n小，不会增加逆序数，当放在后面的位置时（ 0 < i <= n-1），会相应的增加逆序数（因为，新加入的数字n比原来的其他数字都要大），好好想一想，可以想通的，画一画。
然后先按就是数学方面的公式推导过程了，数学不太好的朋友要看仔细了：
①dp【n】【k】=Σdp【n-1】【k-i】（0<=i<=n-1）
②dp【n】【k-1】=Σdp【n-1】【k-1-i】（0<=i<=n-1），（有上个等式得到）
③用①减去②得到：dp【n】【k】-dp【n】【k-1】=dp【n-1】【k】-dp【n-i】【k-n】；
④那么就有：dp【n】【k】=dp【n】【k-1】+dp【n-1】【k】-dp【n-i】【k-n】；
看到最后一步的整理后的等式，有的朋友可能回想，唉，博主这个最后这个式子是不是错了呀，其实没有错，
Σdp【n-1】【k-i】 - Σdp【n-1】【k-1-i】，当先把这两个求个公式全部写出来的时候，因为式子是随着 i 的增大而减小的，所以有的朋友可能是想列举出第一个和最后一个，然后在补充一下中间的几个，有可能会写错，我们可以从 i 减小的方式来写，就不会写错了，就会的出上面的那个最终结果了。
大家是不是已经的出来最后的正确结果了呀！是不是很开心，是不是很兴奋！是不是停不下来！哈哈
这个题大家已经随着博客的讲解推导出来了，那么大家再结合这道题想一想类似的动态规划题目的，解题思路，好好理解一下！
（看代码之前还有一个问题：既然动态规划思想是由上一个状态来推导下一个状态的，那么最初的状态有何而来，怎么得到呢，想一想这道题，一般来说最初的状态由于牵涉的数据都是很小的，一般都可以之间看出结果！！！）
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;const int MOD = 1e9 + 7;
int dp[1003][20004];void make_table()
{for (int i = 1; i <= 1000; i++){dp[i][0] = 1;for (int j = 1; j <= i*(i-1)/2 &&j <= 20000; j++){//这里要注意的是推导出来的公式有的公式是由限制范围的int temp1 = 0, temp2 = 0, temp3 = 0;temp1 = dp[i-1][j];temp2 = dp[i][j-1];if (j-i >= 0) temp3 = dp[i-1][j-i];dp[i][j] = ((temp1 - temp3 + temp2)%MOD + MOD) % MOD;}}
}int main()
{int t;cin >> t;make_table();while (t--){int n, k;scanf("%d%d", &n, &k);printf("%d\n", dp[n][k]);}return 0;
}