結果
問題 | No.2279 OR Insertion |
ユーザー |
![]() |
提出日時 | 2023-04-21 22:00:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 485 ms / 2,000 ms |
コード長 | 588 bytes |
コンパイル時間 | 679 ms |
コンパイル使用メモリ | 82,704 KB |
実行使用メモリ | 80,420 KB |
最終ジャッジ日時 | 2024-11-06 15:29:41 |
合計ジャッジ時間 | 14,199 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
import sys input = sys.stdin.readline mod = 998244353 N = int(input()) S = input().rstrip('\n') ans = 0 for k in range(1, N + 1): dp = [0] * N cs = [0] for i in range(N): if i + 1 - k < 0: dp[i] = (cs[-1] + 1) % mod else: if S[i + 1 - k] == "0": dp[i] = (cs[-1] + 1) % mod else: dp[i] = (cs[-1] - cs[-k]) % mod cs.append((cs[-1] + dp[i]) % mod) num = (pow(2, N - 1, mod) - dp[-1]) % mod ans = (ans + (num * pow(2, k - 1, mod)) % mod) % mod #print(k, num, dp) print(ans)