3014.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3014  User Id:fzk 
Memory:108K  Time:2494MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>

__int64 s[2][4510];

int main( ) {
	int n, m, i, j;
	__int64 *p1 = s[0], *p2 = s[1], *t;
	scanf( "%d%d", &m, &n );
	
	p1[0] = 1;

	for( j=1; j<=m; j++ ) {
		p2[0] = 1;
		for( i=1; i<=n; i++ ) {
			p2[i] = p1[i] + (i>=j?p2[i-j]:0);
			if( p2[i] > (__int64)1000000007*100000000 )
				p2[i] %= 1000000007;
		}
		t = p1;
		p1 = p2;
		p2 = t;
		
	}
	
	printf( "%I64d\n", p1[n]%1000000007 );

	return 0;
}