結果
問題 | No.2772 Appearing Even Times |
ユーザー |
![]() |
提出日時 | 2024-05-31 22:55:16 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,062 bytes |
コンパイル時間 | 400 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 168,032 KB |
最終ジャッジ日時 | 2024-05-31 22:55:23 |
合計ジャッジ時間 | 6,628 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 63 ms
81,224 KB |
testcase_01 | AC | 69 ms
75,740 KB |
testcase_02 | AC | 71 ms
76,156 KB |
testcase_03 | AC | 72 ms
75,796 KB |
testcase_04 | AC | 68 ms
75,852 KB |
testcase_05 | AC | 70 ms
75,904 KB |
testcase_06 | AC | 65 ms
75,940 KB |
testcase_07 | AC | 37 ms
53,708 KB |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
ソースコード
#yukicoder 2772 Appearing Even Times N = input() MOD = 998244353 def brute(N: str): n = int(N) ans = 0 for i in range(1, n + 1): i = str(i) C = [0] * 10 for j in i: C[ int(j) ] ^= 1 if not any(C): ans += 1 return ans def solve(N: str): #DP[i][f][g][S]: Nの下からi桁目まで見たとき、0から9までの数字の出現回数フラグがS、 # f = 以下フラグ # g = 0, 1, 2: leading zerosがない、0が奇数個/偶数個つながる 状態数 #next DP tech. で高速化 DP = [0] * (6 << 10) N = N[::-1] #1桁目を埋める DP[((1 * 3) + 1) << 10 | 1] += 1 now = int(N[0]) for k in range(1, 10): DP[((k <= now) * 3 + 0) << 10 | 1 << k] += 1 #2桁目以降を決定する for i, now in enumerate(N[1:], start = 1): now = int(now) nDP = [0] * (6 << 10) #0をつなげる場合 for S in range(1 << 10): for f in range(2): nf = (now > 0) | f T = S ^ 1 x1 = ((nf * 3) + 1) << 10 | T x2 = x1 + (1 << 10) y1 = ((f * 3) + 0) << 10 | S y2, y3 = y1 + (1 << 10), y1 + (2 << 10) nDP[x1] += DP[y1] + DP[y3] nDP[x1] %= MOD nDP[x2] += DP[y2] nDP[x2] %= MOD #1 - 9をつなげる場合 for S in range(1 << 10): for k in range(1, 10): T = S ^ (1 << k) for f in range(2): nf = (now > k) | ((now == k) & f) x = ((nf * 3) + 0) << 10 | T y1 = ((f * 3) + 0) << 10 | S y2, y3 = y1 + (1 << 10), y1 + (2 << 10) nDP[x] += DP[y1] + DP[y2] + DP[y3] nDP[x] %= MOD DP, nDP = nDP, DP ans = DP[3 << 10] + DP[((1 * 3) + 1) << 10 | 1] + DP[((1 * 3) + 2) << 10] - 1 ans %= MOD return ans print( solve(N) )