結果
問題 | No.2611 Count 01 |
ユーザー |
|
提出日時 | 2024-01-19 17:52:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 5,530 ms / 6,000 ms |
コード長 | 2,847 bytes |
コンパイル時間 | 487 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 233,952 KB |
最終ジャッジ日時 | 2024-09-28 03:41:51 |
合計ジャッジ時間 | 109,068 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
import arrayclass SegmentTree:def __init__(self, n, e):n2 = 1while n2 < n:n2 *= 2self.n = n2self.data = [e] * (n2 * 2)def build(self, a):for i, x in enumerate(a):self.data[i + self.n] = xfor i in range(self.n - 1, 0, -1):self.data[i] = self.data[i * 2] + self.data[i * 2 + 1]def update(self, i, x):k = i + self.nself.data[k] = xwhile k > 1:k //= 2self.data[k] = self.data[k * 2] + self.data[k * 2 + 1]def query(self, l, r, ls, rs):l += self.nr += self.nwhile l < r:if l & 1:ls += self.data[l]l += 1if r & 1:r -= 1rs = self.data[r] + rsl //= 2r //= 2return ls + rsMOD = 998244353class Vec:def __init__(self, a):self.a = adef __add__(self, other):if isinstance(other, Matrix):result = self.a[:]for i in range(len(self.a)):for j in range(i):result[j] += self.a[i] * other.a[i * (i - 1) // 2 + j]for i in range(len(self.a)):result[i] %= MODreturn Vec(result)return sum(x * y for x, y in zip(self.a, other.a)) % MODclass Matrix:size = 6def __init__(self, a):self.a = adef __add__(self, other):if isinstance(other, Vec):result = other.a[:]for i in range(self.size):for j in range(i):result[i] += self.a[i * (i - 1) // 2 + j] * other.a[j]result[i] %= MODreturn Vec(result)result = array.array('l', [i + j for i, j in zip(self.a, other.a)])for i in range(self.size):for j in range(i):ij = i * (i - 1) // 2 + jfor k in range(j + 1, i):result[ij] += self.a[i * (i - 1) // 2 + k] * other.a[k * (k - 1) // 2 + j]result[ij] %= MODreturn Matrix(result)node = [Matrix(array.array('l', [1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1])),Matrix(array.array('l', [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1])),]identity = Matrix(array.array('l', [0] * 15))n, q = map(int, input().split())s = input()s_seq = [int(x) for x in s]st = SegmentTree(n, identity)st.build([node[x] for x in s_seq])for _ in range(q):t, *args = map(int, input().split())if t == 1:i = args[0] - 1s_seq[i] = 1 - s_seq[i]st.update(i, node[s_seq[i]])else:l, r = argsans = st.query(l - 1, r, Vec(array.array('l', [0, 0, 0, 0, 0, 1])), Vec(array.array('l', [1, 0, 0, 0, 0, 0])))print(ans)