原题：

Problem Description

我们知道，在编程中，我们时常需要考虑到时间复杂度，特别是对于循环的部分。例如， 如果代码中出现 for( i=1; i<=n; i++) OP ; 那么做了n次OP运算，如果代码中出现 for(i=1; i<=n; i++) for(j=i+1; j<=n; j++) OP; 那么做了n*(n-1)/2 次OP 操作。 现在给你已知有m层for循环操作，且每次for中变量的起始值是上一个变量的起始值＋1（第一个变量的起始值是1），终止值都是一个输入的n，问最后OP有总共多少计算量。

Input

有T组case，T<=10000。每个case有两个整数m和n，0 < m <= 2000，0 < n <= 2000.

Output

对于每个case，输出一个值，表示总的计算量，也许这个数字很大，那么你只需要输出除1007留下的余数即可。

Sample Input

2 1 3 2 3

Sample Output

3 3

解题思路：

杨辉三角 重要概念：

第n行数字和为2^(n-1)。第n行的m个数可表示为C(n-1，m-1)，即为从n-1个不同元素中取m-1个元素的组合数。第n行的第m个数和第n-m+1个数相等 ，为组合数性质之一。每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即 C(n+1, i) = C(n, i) + C(n, i-1)。二项式定理：(a+b)^n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。

解题思路：

这道题利用 排列组合Cn(m)（也就是从n个元素中任取m个元素）的思考方式，实现过程用杨辉三角。 假设现在有4个 小球 A B C D 要从中取2个 用排列组合的方式：先取A 然后可以依次取 B C D ；接下来 取B 然后可以依次取C D ； 接下来取C ，但只能取剩下的D； 这样就有3 + 2 + 1 = 6 种组合C( 4 , 2 ) = C( 3 , 1) + C( 3 , 2) = 3 + 3。 这里的4 就是题目的n， 这里的2就是题目的m（循环次数）； 所以题目问的操作次数 也就是 问有多少种取球方式；

代码：

#include <cstdio> int result[2001][2001]; void preprocessing()//预处理(杨辉三角) { for (int i = 0; i < 2001; i++) result[i][0] = result[i][i] = 1; for (int i = 2; i < 2001; i++) for (int j = 1; j < i; j++) result[i][j] = (result[i - 1][j] + result[i - 1][j - 1]) % 1007; } int main() { preprocessing(); int T, m, n; scanf_s("%d", &T); while (T--) { scanf_s("%d%d", &m, &n); printf("%d\n", result[n][m]); } }