結果
問題 | No.2867 NOT FOUND 404 Again |
ユーザー |
|
提出日時 | 2024-08-30 21:53:22 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,080 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 86,228 KB |
最終ジャッジ日時 | 2024-08-30 21:53:28 |
合計ジャッジ時間 | 4,983 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 1 TLE * 1 -- * 16 |
ソースコード
from math import e import sys, time, random from collections import deque, Counter, defaultdict def debug(*x):print('debug:',*x, file=sys.stderr) input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 61 - 1 mod = 998244353 N = input() n = len(N) dp = [[0] * 100 for _ in range(2)] dp[0][0] = 1 for i in range(n): edp = [[0] * 100 for _ in range(2)] ni = int(N[i]) for j in range(100): to = 10 * j for k in range(ni + 1): if to + k != 404: nx = (to + k) % 100 if k < ni: edp[1][nx] += dp[0][j] edp[1][nx] %= mod elif k == ni: edp[0][nx] += dp[0][j] edp[0][nx] %= mod for k in range(10): if to + k != 404: nx = (to + k) % 100 edp[1][nx] += dp[1][j] edp[1][nx] %= mod dp = edp ans = sum(dp[0]) + sum(dp[1]) - 1 ans %= mod print(ans)