2016HUAS_ACM暑假集训4A – 递推

利用组合公式C(n,m)=C(n-1,m)+C(n-1,m-1)。也就是从n个数里面选择m个数、按递增方式放在每一层循环。

杨辉三角+二项式定理，还真是挺有“意思”的一道题。说实话，非原创。见谅…..

题目大意：一个循环结构有m层，第一层是1~n，以后每加一层，循环变量的初值都都在上一层的基础上加1。

例如：第一层是1~n，那么第二层就是2~n，以此类推。求出m层的循环次数（答案对1007取模）。

Sample Input

2                                           //测试案例数T

1  3                                       //m和n

2  3

Sample Output                       //循环次数

3

3

#include<iostream>#include<cstdio>using namespace std;int t,m,n,i,j;][];void slove(){    ans[][]=;    ;i<=;i++)    {        ans[i][]=;        ;j<=;j++)            ans[i][j]=(ans[i-][j-]+ans[i-][j])%;    }}int main(){    slove();    cin>>t;    while(t--)    {        cin>>m>>n;        printf("%d\n",ans[n][m]);    }    ;}