【杭电】[1799]循环多少次？

问题描述

问题分析

刚开始没推导对
看题解说是组合数

纠结了一会没看出来怎么推的
然后通过杨辉三角及这个手动算的关系
发现满足 f(n,m)=f(n-1,m)+f(n-1,m-1)
所以也就是组合数

之后大数取余也可以轻松写了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
int C[2020][2020];
int main() {
	C[0][0]=1;
	C[0][1]=0;
	for(int i=1; i<2010; i++) {
		for(int j=0; j<=i; j++) {
			if(j==0)
				C[i][j]=1;
			else
				C[i][j]=(C[i-1][j]+C[i-1][j-1])%1007;
		}
	}
	int T;
	scanf("%d",&T);
	while(T--) {
		int m,n;
		scanf("%d %d",&m,&n);
		printf("%d\n",C[n][m]);
	}
	return 0;
}

题目地址:【杭电】[1799]循环多少次？