結果
問題 | No.2772 Appearing Even Times |
ユーザー |
![]() |
提出日時 | 2024-05-31 23:14:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 140 ms / 4,000 ms |
コード長 | 1,111 bytes |
コンパイル時間 | 290 ms |
コンパイル使用メモリ | 82,276 KB |
実行使用メモリ | 87,984 KB |
最終ジャッジ日時 | 2024-12-21 01:31:21 |
合計ジャッジ時間 | 3,234 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
S = list(input())S = list(map(int, S))N = len(S)dp = [[[0] * 2 for _ in range(11)] for _ in range(N)]dp[0][1][0] = S[0] - 1dp[0][0][1] = 1mod = 998244353L = [0] * 10L[S[0]] += 1for i in range(1, N):for j in range(11):# 真に小さい場合# 奇数個の数が増えるif j + 1 <= 10:dp[i][j + 1][0] += dp[i - 1][j][0] * (10 - j)dp[i][j + 1][0] += dp[i - 1][j][1] * 9dp[i][j + 1][0] %= mod# 奇数個の数が減るif j:dp[i][j - 1][0] += dp[i - 1][j][0] * jdp[i][j - 1][0] %= mod# leading0が続くdp[i][j][1] += dp[i - 1][j][1]dp[i][j][1] %= mod# Nちょうどから遷移してくる場合pj = sum(L)for j in range(S[i]):L[j] ^= 1nj = sum(L)dp[i][nj][0] += 1dp[i][nj][0] %= modL[j] ^= 1# Nちょうどの場合の奇数個を管理L[S[i]] ^= 1ans = dp[N - 1][0][0]if sum(L) == 0:ans += 1ans %= modprint(ans)