题目

题意：给出n,m，其中m表示有几层循环，求循环的次数

①如果代码中出现

for(i=1;i<=n;i++) OP ;

那么做了n次OP运算；

②如果代码中出现

fori=1;i<=n; i++)

  for(j=i+1;j<=n; j++) OP;

那么做了n*(n-1)/2 次OP 操作

如果有m层循环，那OP操作：n*(n-1)*(n-2)*.....(n-m+1)/m*(m-1)*...*1 ,即: n!/m!(n-m)! 发现是一个组合数：

组合数通项公式：Cnm= n! / m!*(n-m)!;

组合数递推公式：Cnm=Cnm−1+Cn−1m−1

即用dp,递推关系为：C(n,m) = C(n-1,m-1) + C(n-1, m) ,其中 C(n,1)=n; C(n,n)=1; C(n,0)=1

#include <cstdio>

#include <iostream>

using namespace std;

#include <algorithm>

const int MOD = 1007;

int C[2010][2010];

void solve()

{

    C[0][0]=1;

    for(int i=1;i<=2000;i++){

        C[i][0]=1;

        for(int j=1;j<=2000;j++)

            C[i][j]=(C[i-1][j-1] + C[i-1][j])%MOD;

        }

}

int main()

{

   int m,n;

   int T;

   solve();

   scanf("%d",&T);

   while(T--)

   {

       scanf("%d%d",&m,&n);

       printf("%d\n",C[n][m]);

   }

    return 0;

}