結果

問題 No.336 門松列列
ユーザー testtest
提出日時 2016-02-07 11:51:06
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 1,545 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 27,612 KB
実行使用メモリ 98,692 KB
最終ジャッジ日時 2023-09-02 18:45:04
合計ジャッジ時間 1,484 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
98,620 KB
testcase_01 AC 46 ms
98,676 KB
testcase_02 AC 47 ms
98,676 KB
testcase_03 AC 47 ms
98,648 KB
testcase_04 AC 47 ms
98,660 KB
testcase_05 AC 47 ms
98,692 KB
testcase_06 AC 47 ms
98,656 KB
testcase_07 AC 46 ms
98,656 KB
testcase_08 AC 47 ms
98,656 KB
testcase_09 AC 47 ms
98,628 KB
testcase_10 AC 47 ms
98,660 KB
testcase_11 AC 47 ms
98,648 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdint.h>

typedef uint64_t bigint;

int const M = 2020; 
#define mod 1000000007
bigint f[2][M][M], g[2][M]; 
bigint C[M][M]; 

void initC(){
	bigint *p, *q; 
	for(int n = 0; n < M; ++n){
		C[n][0] = 1; p = &C[n][0]; q = &C[n - 1][0];  
		for(int i = 1; i <= n; ++i){
			p[i] = q[i] + q[i - 1]; p[i] %= mod; 
		}
	}
}

void initFG(){
	g[0][1] = 1; g[1][1] = 1; f[0][1][1] = 1; f[1][1][1] = 1; 

	g[0][0] = 1; g[1][0] = 1; 

	bigint *p, *q, *r, *s; 
	for(int n = 2; n <= 2016; ++n){
		p = &f[0][n][0]; q = &C[n-1][0]; r = &g[0][0]; s = &g[0][0]; 
		for(int i = 2; i <= n; i += 2){ 
			p[i] = q[i - 1] * r[i - 1]; p[i] %= mod; 
			p[i] *= s[n - i]; p[i] %= mod; 
		}
		p = &f[1][n][0]; q = &C[n-1][0]; r = &g[1][0]; s = &g[0][0]; 
		for(int i = 1; i <= n; i += 2){ 
			p[i] = q[i - 1] * r[i - 1]; p[i] %= mod; 
			p[i] *= s[n - i]; p[i] %= mod; 
		}
		p = &g[0][n]; q = &f[0][n][0]; r = &g[1][n]; s = &f[1][n][0]; 
		for(int i = 1; i <= n; ++i){ 
			*p += q[i]; *p %= mod; 
			*r += s[i]; *r %= mod; 
		}
	}
}

void first_init(){
	bigint *p = &f[0][0][0];
	for(int N = 2 * M * M, i = 0; i < N; ++i){ p[i] = 0; }
	p = &g[0][0]; 
	for(int N = 2 * M, i = 0; i < N; ++i){ p[i] = 0; }
	p = &C[0][0]; 
	for(int N = M * M, i = 0; i < N; ++i){ p[i] = 0; }

	initC(); 
	initFG(); 
}

int get(int N){
	if(2 >= N || 2016 < N){ return 0; }
	bigint ret = g[0][N] + g[1][N]; ret %= mod; 
	return int(ret); 
}

int main(int argc, char *argv[]){
	int N = 0; 
	first_init(); 
	scanf("%d", &N); 
	printf("%d\n", get(N)); 
	return 0;
}
0