結果
問題 | No.336 門松列列 |
ユーザー | test |
提出日時 | 2016-02-07 11:51:06 |
言語 | C++11 (gcc 11.4.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 42 ms
97,152 KB |
testcase_01 | AC | 41 ms
97,280 KB |
testcase_02 | AC | 40 ms
97,152 KB |
testcase_03 | AC | 40 ms
97,160 KB |
testcase_04 | AC | 39 ms
97,280 KB |
testcase_05 | AC | 40 ms
97,160 KB |
testcase_06 | AC | 41 ms
97,156 KB |
testcase_07 | AC | 41 ms
97,280 KB |
testcase_08 | AC | 39 ms
97,280 KB |
testcase_09 | AC | 39 ms
97,280 KB |
testcase_10 | AC | 40 ms
97,152 KB |
testcase_11 | AC | 42 ms
97,164 KB |
コンパイルメッセージ
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); | ~~~~~^~~~~~~~~~
ソースコード
#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; }