結果

問題 No.2867 NOT FOUND 404 Again
ユーザー H3PO4H3PO4
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
52,316 KB
testcase_01 AC 35 ms
52,892 KB
testcase_02 AC 35 ms
52,936 KB
testcase_03 AC 113 ms
77,556 KB
testcase_04 AC 115 ms
78,212 KB
testcase_05 AC 109 ms
77,332 KB
testcase_06 AC 117 ms
77,960 KB
testcase_07 AC 112 ms
77,968 KB
testcase_08 AC 115 ms
77,940 KB
testcase_09 AC 113 ms
77,940 KB
testcase_10 AC 116 ms
78,000 KB
testcase_11 AC 113 ms
77,848 KB
testcase_12 AC 111 ms
77,880 KB
testcase_13 AC 117 ms
77,960 KB
testcase_14 AC 111 ms
78,076 KB
testcase_15 AC 110 ms
77,552 KB
testcase_16 AC 140 ms
78,084 KB
testcase_17 AC 113 ms
77,948 KB
testcase_18 AC 78 ms
77,416 KB
testcase_19 AC 73 ms
77,408 KB
権限があれば一括ダウンロードができます

ソースコード

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