結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-05 21:54:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 129 ms / 3,000 ms |
コード長 | 1,873 bytes |
コンパイル時間 | 332 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 78,148 KB |
最終ジャッジ日時 | 2024-10-07 01:37:36 |
合計ジャッジ時間 | 4,067 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
mod = 1000000007eps = 10 ** -9def main():import sysinput = sys.stdin.readlineN = input().rstrip('\n')L = len(N)dp0 = [[[0] * (L + 1) for _ in range(3)] for _ in range(3)]dp1 = [[[0] * (L + 1) for _ in range(3)] for _ in range(3)]dp0[0][0][0] = 1for i in range(1, L):dp1[0][0][i] = 1for i, n in enumerate(N):n = int(n)for j in range(1, 10):for num_2 in range(3):for num_5 in range(3):if j % 5 == 0:num_5_new = min(2, num_5 + 1)else:num_5_new = num_5if j%4 == 0:num_2_new = min(2, num_2 + 2)elif j%2 == 0:num_2_new = min(2, num_2 + 1)else:num_2_new = num_2if j < n:dp1[num_2_new][num_5_new][i+1] = (dp1[num_2_new][num_5_new][i+1] +dp1[num_2][num_5][i] +dp0[num_2][num_5][i])%modelif j == n:dp1[num_2_new][num_5_new][i + 1] = (dp1[num_2_new][num_5_new][i + 1] +dp1[num_2][num_5][i]) % moddp0[num_2_new][num_5_new][i+1] = (dp0[num_2_new][num_5_new][i + 1] +dp0[num_2][num_5][i]) % modelse:dp1[num_2_new][num_5_new][i + 1] = (dp1[num_2_new][num_5_new][i + 1] +dp1[num_2][num_5][i]) % modprint((dp0[2][2][-1] + dp1[2][2][-1])%mod)if __name__ == '__main__':main()