結果
問題 | No.2060 AND Sequence |
ユーザー |
![]() |
提出日時 | 2022-08-26 22:02:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 703 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 52,480 KB |
最終ジャッジ日時 | 2024-10-13 22:37:36 |
合計ジャッジ時間 | 3,212 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
# n, m逆にしちゃった(このコードを見てる人は注意!) mod = 998244353 m, n = map(int,input().split()) ns = bin(n)[2:] size = len(ns) # A[N] = K に固定すると, pow(N, popcount) # 桁DP, popcountで主客転倒する dp = [0] * 31 tmp = 0 for i in range(size): ndp = [0] * 31 # 継続 for k in range(30): ndp[k+1] += dp[k] for k in range(31): ndp[k] += dp[k] # 子供 if i > 0: ndp[1] += 1 # 新規 if i > 0 and ns[i] == "1": ndp[tmp] += 1 for k in range(31): dp[k] = ndp[k] % mod if ns[i] == "1": tmp += 1 dp[0] += 1 dp[0] %= mod dp[tmp] += 1 dp[tmp] %= mod ans = 0 for i in range(31): ans += pow(m, i, mod) * dp[i] ans %= mod print(ans)