[TIOJ] 1103. F.假日的奇想曲

題目連結:http://tioj.infor.org/problems/1103

---

先說顯然本題不能開一個$n \times 2n$的矩陣，不然你一定會MLE掉，那該怎麼做呢？
大家高中可能學過類似這種題目的做法:填格子，沒錯，就是填格子，每次從左到右填一橫條，把它下面跟他左邊(也就是相鄰的)的值加起來，那顯然我們每次都只會用到它下面那條，其他用完就可以扔了，所以不妨用兩條滾動，然後記得先把表完全建好，不然每次要問都要建一次，複雜度會變成$O(t \times n^2)$，明顯會慘掉..

#include <bits/stdc++.h>
using namespace std;
#define modBASE 10000
#define N 10000

int graph[2][N + 10];
int val[N + 10];

int main(){
	int sz=0;
	for(int i=0;i<=N;i++)
		graph[0][i]=1;
	for(int i=1;i<=2*N;i++){
		if((i-1)%2==0)sz++;
		for(int j=0;j<=N;j++)
			graph[i%2][j]=0;
		for(int j=sz;j<=N;j++){
			graph[i%2][j]=graph[i%2][j-1];
			graph[i%2][j]%=modBASE;
			graph[i%2][j]+=graph[(i-1)%2][j];
			graph[i%2][j]%=modBASE;
			if(j*2==i)val[j]=graph[i%2][j];
		}
	}
	int n;
	scanf("%d",&n);
	while(n!=0){
		if(n>=8)
			printf("%04d\n",val[n]);
		else
			printf("%d\n",val[n]);
		scanf("%d",&n);
	}
	return 0;
}