結果
問題 | No.2219 Re:010 |
ユーザー |
|
提出日時 | 2023-02-17 22:10:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 262 ms / 2,000 ms |
コード長 | 763 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,908 KB |
実行使用メモリ | 123,608 KB |
最終ジャッジ日時 | 2024-07-19 13:20:47 |
合計ジャッジ時間 | 4,173 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
s = input() mod = 998244353 ans = 0 n = len(s) pre = [] hate = [] last = 0 nowh = 0 for i in range(n): si = s[i] hate.append(last) if si == "0": last += pow(2, nowh, mod) elif si == "?": last *= 2 last += pow(2, nowh, mod) nowh += 1 last %= mod pre.append(last) suf = [] hates = [] nowh = 0 last = 0 for i in range(n)[::-1]: si = s[i] hates.append(last) if si == "0": last += pow(2, nowh, mod) elif si == "?": last *= 2 last += pow(2, nowh, mod) nowh += 1 last %= mod suf.append(last) suf = suf[::-1] hates = hates[::-1] ans = 0 for i in range(1,n-1): if s[i] == "1": ans += pre[i] * suf[i] % mod ans %= mod elif s[i] == "?": ans += hate[i] * hates[i] % mod ans %= mod print(ans)