結果

問題 No.2867 NOT FOUND 404 Again
ユーザー H3PO4
提出日時 2024-08-30 23:11:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 2,052 bytes
コンパイル時間 248 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 12,924 KB
最終ジャッジ日時 2024-08-30 23:12:21
合計ジャッジ時間 49,723 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 3 WA * 15
権限があれば一括ダウンロードができます

ソースコード

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