結果

問題 No.2772 Appearing Even Times
ユーザー detteiuudetteiuu
提出日時 2024-05-31 23:02:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 3,823 ms / 4,000 ms
コード長 827 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 403,276 KB
最終ジャッジ日時 2024-05-31 23:02:59
合計ジャッジ時間 47,146 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
61,884 KB
testcase_01 AC 52 ms
63,976 KB
testcase_02 AC 57 ms
64,684 KB
testcase_03 AC 51 ms
64,976 KB
testcase_04 AC 52 ms
63,740 KB
testcase_05 AC 52 ms
64,012 KB
testcase_06 AC 52 ms
64,416 KB
testcase_07 AC 43 ms
59,872 KB
testcase_08 AC 3,799 ms
403,276 KB
testcase_09 AC 3,823 ms
403,180 KB
testcase_10 AC 47 ms
60,548 KB
testcase_11 AC 53 ms
63,772 KB
testcase_12 AC 3,750 ms
402,936 KB
testcase_13 AC 3,742 ms
401,036 KB
testcase_14 AC 3,791 ms
402,692 KB
testcase_15 AC 3,793 ms
401,260 KB
testcase_16 AC 3,747 ms
403,080 KB
testcase_17 AC 3,774 ms
402,532 KB
testcase_18 AC 3,815 ms
402,440 KB
testcase_19 AC 3,765 ms
401,892 KB
testcase_20 AC 3,749 ms
397,276 KB
testcase_21 AC 3,742 ms
399,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = input()

dp = [[[[0]*(1<<10) for _ in range(2)] for _ in range(2)] for _ in range(len(N)+1)]
dp[0][0][0][0] = 1
MOD = 998244353
for i in range(len(N)):
    for zero in range(2):
        for small in range(2):
            for j in range(1<<10):
                if dp[i][zero][small][j] >= 1:
                    X = 10 if small else int(N[i])+1
                    for k in range(X):
                        if zero == 0 and k == 0:
                            dp[i+1][0][1][0] += dp[i][zero][small][j]
                            dp[i+1][0][1][0] %= MOD
                        else:
                            dp[i+1][zero or k>0][small or k<int(N[i])][j^(1<<k)] += dp[i][zero][small][j]
                            dp[i+1][zero or k>0][small or k<int(N[i])][j^(1<<k)] %= MOD

print((dp[-1][1][0][0]+dp[-1][1][1][0])%MOD)
0