글 읽기 - T * C * D 시간

skynet 3년 전 0

T * c * d 시간으로 짰는데 왜 때문에 시간초과가 나는걸까요.....

이거보다 더 빠른 알고리즘이 가능한가요? 병렬처리?!!!

버퍼리딩 해야되나요?

곱연산을 모듈러 하는 방법을 써야 하나요?

/// 9341ZZ

#include <cstdio>
#include <memory.h>

#define MAXIMUM 1000000009

int main()
{
	int t;
	scanf("%d", &t);
	while (t--) {
		int a, b, c, d;
		int zzNow[101];
		int c0, temp;
		scanf("%d %d %d %d", &a, &b, &c, &d);
		
		for (int i = 0; i <= c; i++)
			zzNow[i] = a;
		if (d >= 2) {
			zzNow[0] = b;
			c0 = a;
			for (int i = 1; i <= c; i++)
				zzNow[i] = (zzNow[i] + zzNow[i - 1]) % MAXIMUM;
		}
		for (int j = 3; j <= d; j++) {
			temp = zzNow[0];
			zzNow[0] = (zzNow[0] + c0) % MAXIMUM;
			c0 = temp;
			for (int i = 1; i <= c; i++)
				zzNow[i] = (zzNow[i] + zzNow[i - 1]) % MAXIMUM;
		}
		printf("%d\n", zzNow[c]);
	}
}


/*

0 1 a
0 2 b
0 3 ab
0 4 abb
0 5 ababb
0 6 abbababb
0 7 ababbabbababb

1 1 = 01
1 2 = 01 02
1 3 = 01 02 03
1 4 = 01 02 03 04

2 1 = 11
2 2 = 11 12
2 3 = 11 12 13
2 4 = 11 12 13 14

	1	2	3		4				5	
0	a	b	ab		abb				aabbb
1	a	ab	aabb	aaabbb			aaaaabbbbbbb
2	a	aab	aaaabbb	aaaaaaabbbbbb
3	

조합?!!

*/