結果

提出番号	217
提出者	kim
言語	C++
提出日時	2017-07-11 14:41:31
問題名	(15)掛け算フィボナッチ
結果	AC
点数	100%

---

テストケース

ソースコード

#include <cstdio>
#include <vector>
using namespace std;


int main() {
	int Q;
	vector<long long> fibo,fibo_product;

	scanf("%d",&Q);
	if(Q<=1) {
		printf("%d\n",Q);
		return 0;
	}
	fibo.resize(Q+1);
	fibo_product.resize(Q+1);
	fibo[0]=0;
	fibo[1]=1;
	fibo_product[1]=1;
	for(int i=2; i<Q+1; ++i) {
		fibo[i]=(fibo[i-1]+fibo[i-2])%1000000007;
		fibo_product[i]=(fibo_product[i-1]*fibo[i])%1000000007;
	}
	printf("%lld\n",fibo_product[Q]);
	return 0;
}