結果
問題 |
No.1811 EQUIV Ten
|
ユーザー |
👑 |
提出日時 | 2021-12-29 14:55:03 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 29 ms / 2,000 ms |
コード長 | 545 bytes |
コンパイル時間 | 996 ms |
コンパイル使用メモリ | 29,440 KB |
実行使用メモリ | 14,464 KB |
最終ジャッジ日時 | 2024-11-20 06:39:50 |
合計ジャッジ時間 | 2,407 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <stdio.h> const int Mod = 1000000007; int main() { int N; scanf("%d", &N); int i, j, dp[200001][16] = {}; long long ans = 0, tmp; for (i = 5, dp[4][10] = 1; i <= N; i++) { for (j = 0; j < 16; j++) { dp[i][j*2%16] += dp[i-1][j]; dp[i][(j*2+1)%16] += dp[i-1][j]; } dp[i][10] = 0; for (j = 0; j < 16; j++) if (dp[i][j] >= Mod) dp[i][j] -= Mod; } for (i = N, tmp = 1; i >= 1; i--, tmp = tmp * 2 % Mod) for (j = 0; j < 16; j++) ans += tmp * dp[i][j] % Mod; printf("%lld\n", ans % Mod); fflush(stdout); return 0; }