結果

問題 No.2867 NOT FOUND 404 Again
ユーザー H3PO4H3PO4
提出日時 2024-08-30 23:11:31
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 2,052 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 12,924 KB
最終ジャッジ日時 2024-08-30 23:12:21
合計ジャッジ時間 49,723 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
10,752 KB
testcase_01 WA -
testcase_02 AC 30 ms
10,752 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 2,971 ms
12,924 KB
testcase_19 AC 2,551 ms
12,792 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  # 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