結果

問題 No.2867 NOT FOUND 404 Again
コンテスト
ユーザー H3PO4
提出日時 2024-08-30 23:14:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 140 ms / 3,000 ms
コード長 2,147 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 78,212 KB
最終ジャッジ日時 2024-08-30 23:14:52
合計ジャッジ時間 3,498 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = input()
MOD = 998244353

dp_smaller = 0  # N未満確定, 4も40もなし
dp_smaller_4 = 0  # N未満確定, 4が出現
dp_smaller_40 = 0  # N未満確定, 40が出現
dp_equal = 1  # 上位x桁がNと一致, 4も40もなし
dp_equal_4 = 0  # 上位x桁がNと一致, 4が出現
dp_equal_40 = 0  # 上位x桁がNと一致, 40が出現

for n in N:
    n = int(n)
    new_dp_smaller = (
        dp_smaller * 9  # smallerの4以外
        + dp_smaller_4 * 8  # smaller_4の0,4以外
        + dp_smaller_40 * 9  # smaller_40の4以外
        + dp_equal * (n if n <= 4 else n - 1)  # equalのn未満かつ4以外
        + dp_equal_4 * (max(0, n - 1) if n <= 4 else n - 2)  # equal_4のn未満かつ0,4以外
        + dp_equal_40 * (n if n <= 4 else n - 1)  # equal_40のn未満かつ4以外
    ) % MOD
    new_dp_smaller_4 = (
        dp_smaller  # smallerの4
        + dp_smaller_4  # smaller_4の4
        + dp_equal * (0 if n <= 4 else 1)  # equalのn未満かつ4
        + dp_equal_4 * (0 if n <= 4 else 1)  # equal_4のn未満かつ4
    ) % MOD
    new_dp_smaller_40 = (
        dp_smaller_4  # smaller_4の0
        + dp_equal_4 * (0 if n == 0 else 1)  # equal_4のn未満かつ0
    ) % MOD
    new_dp_equal = (
        dp_equal * (1 if n != 4 else 0)  # equalの4以外
        + dp_equal_4 * (1 if (n != 0 and n != 4) else 0)  # equal_4の0,4以外
        + dp_equal_40 * (1 if n != 4 else 0)  # equal_40の4以外
    ) % MOD
    new_dp_equal_4 = (
        dp_equal * (1 if n == 4 else 0)  # equalの4
        + dp_equal_4 * (1 if n == 4 else 0)  # equal_4の4
    ) % MOD
    new_dp_equal_40 = (
        dp_equal_4 * (1 if n == 0 else 0)  # equal_4の0
    ) % MOD

    dp_smaller = new_dp_smaller
    dp_smaller_4 = new_dp_smaller_4
    dp_smaller_40 = new_dp_smaller_40
    dp_equal = new_dp_equal
    dp_equal_4 = new_dp_equal_4
    dp_equal_40 = new_dp_equal_40
# print(dp_smaller , dp_smaller_4 , dp_smaller_40 , dp_equal , dp_equal_4 , dp_equal_40)
print(
    (
        dp_smaller
        + dp_smaller_4
        + dp_smaller_40
        + dp_equal
        + dp_equal_4
        + dp_equal_40
        - 1
    )
    % MOD
)
0