結果

問題 No.336 門松列列
コンテスト
ユーザー test
提出日時 2016-02-07 11:51:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 1,545 bytes
コンパイル時間 127 ms
コンパイル使用メモリ 24,704 KB
実行使用メモリ 97,280 KB
最終ジャッジ日時 2024-06-12 01:12:11
合計ジャッジ時間 1,153 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:67:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   67 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~

ソースコード

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