結果
問題 | No.2219 Re:010 |
ユーザー | Shirotsume |
提出日時 | 2023-02-14 07:44:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 1,369 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 96,116 KB |
最終ジャッジ日時 | 2024-07-16 17:33:56 |
合計ジャッジ時間 | 3,469 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
55,116 KB |
testcase_01 | AC | 39 ms
54,232 KB |
testcase_02 | AC | 40 ms
54,116 KB |
testcase_03 | AC | 101 ms
85,108 KB |
testcase_04 | AC | 87 ms
79,396 KB |
testcase_05 | AC | 129 ms
96,116 KB |
testcase_06 | AC | 88 ms
82,528 KB |
testcase_07 | AC | 104 ms
90,044 KB |
testcase_08 | AC | 94 ms
84,552 KB |
testcase_09 | AC | 96 ms
84,264 KB |
testcase_10 | AC | 115 ms
95,392 KB |
testcase_11 | AC | 104 ms
92,120 KB |
testcase_12 | AC | 111 ms
92,480 KB |
testcase_13 | AC | 99 ms
86,688 KB |
testcase_14 | AC | 98 ms
86,532 KB |
testcase_15 | AC | 103 ms
86,468 KB |
testcase_16 | AC | 101 ms
86,208 KB |
testcase_17 | AC | 102 ms
86,408 KB |
testcase_18 | AC | 60 ms
72,728 KB |
testcase_19 | AC | 74 ms
79,884 KB |
testcase_20 | AC | 86 ms
86,196 KB |
testcase_21 | AC | 40 ms
54,056 KB |
testcase_22 | AC | 40 ms
55,324 KB |
testcase_23 | AC | 38 ms
55,356 KB |
ソースコード
import sysfrom collections import deque, Counterinput = lambda: sys.stdin.readline().rstrip()ii = lambda: int(input())mi = lambda: map(int, input().split())li = lambda: list(mi())inf = 2 ** 63 - 1mod = 998244353class Cumsum1d():def __init__(self, A):self.n = len(A)self.Suma = [0] * (self.n + 1)for i in range(self.n):self.Suma[i + 1] += self.Suma[i] + A[i]def query(self, l, r):#0-indexedreturn self.Suma[r] - self.Suma[l]def get(self, i):return self.Suma[i + 1] - self.Suma[i]def __getitem__(self, p):if isinstance(p, int):return self.get(p)else:return self.query(p.start, p.stop)s = input()n = len(s)d2 = pow(2, mod - 2, mod)zero = Cumsum1d([1 if s[i] == '0' else 0 for i in range(n)])one = Cumsum1d([1 if s[i] == '1' else 0 for i in range(n)])wild = Cumsum1d([1 if s[i] == '?' else 0 for i in range(n)])ans = 0for i in range(n):if s[i] == '1' or s[i] == '?':cnt = zero[0:i] * zero[i+1:n]cnt += wild[0:i] * zero[i+1:n] % mod * d2cnt %= modcnt += zero[0:i] * wild[i+1:n] % mod * d2cnt += wild[0:i] * wild[i+1:n] % mod * d2 % mod * d2cnt %= modif s[i] == '?':cnt *= d2ans += cntprint(ans * pow(2, wild[0:n], mod) % mod)