結果
問題 | No.533 Mysterious Stairs |
ユーザー |
|
提出日時 | 2021-01-16 06:53:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 270 ms / 5,000 ms |
コード長 | 964 bytes |
コンパイル時間 | 297 ms |
コンパイル使用メモリ | 82,548 KB |
実行使用メモリ | 166,884 KB |
最終ジャッジ日時 | 2024-11-27 05:59:50 |
合計ジャッジ時間 | 5,685 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#region Header#!/usr/bin/env python3# from typing import *import sysimport ioimport mathimport collectionsimport decimalimport itertoolsfrom queue import PriorityQueueimport bisectimport heapqdef input():return sys.stdin.readline()[:-1]sys.setrecursionlimit(1000000)#endregion# _INPUT = """100# """# sys.stdin = io.StringIO(_INPUT)MOD = 1000000007def main():N = int(input())dp = [[0, 0, 0] for _ in range(max(N+1, 5))]dp[0][0] = 1dp[0][1] = 0dp[0][2] = 0dp[1][0] = 1dp[1][1] = 0dp[1][2] = 0dp[2][0] = 0dp[2][1] = 1dp[2][2] = 0dp[3][0] = 1dp[3][1] = 1dp[3][2] = 1for i in range(4, N+1):dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % MODdp[i][1] = (dp[i-2][0] + dp[i-2][2]) % MODdp[i][2] = (dp[i-3][0] + dp[i-3][1]) % MODprint(sum(dp[N]) % MOD)if __name__ == '__main__':main()