結果

問題 No.2611 Count 01
ユーザー MitarushiMitarushi
提出日時 2024-01-19 17:26:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,046 bytes
コンパイル時間 432 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 519,524 KB
最終ジャッジ日時 2024-09-28 03:39:31
合計ジャッジ時間 8,966 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 19 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self, n, e):
        n2 = 1
        while n2 < n:
            n2 *= 2
        self.n = n2
        self.data = [e] * (n2 * 2)

    def build(self, a):
        for i, x in enumerate(a):
            self.data[i + self.n] = x
        for 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.n
        self.data[k] = x
        while k > 1:
            k //= 2
            self.data[k] = self.data[k * 2] + self.data[k * 2 + 1]

    def query(self, l, r, ls, rs):
        l += self.n
        r += self.n
        while l < r:
            if l & 1:
                ls += self.data[l]
                l += 1
            if r & 1:
                r -= 1
                rs = self.data[r] + rs
            l //= 2
            r //= 2
        return ls + rs


MOD = 998244353

class Vec:
    def __init__(self, a):
        self.a = a

    def __add__(self, other):
        if isinstance(other, Matrix):
            result = [0] * len(self.a)
            for i in range(len(self.a)):
                for j in range(i + 1):
                    result[j] += self.a[i] * other.a[i][j]
            for i in range(len(self.a)):
                result[i] %= MOD
            return Vec(result)
        return sum(x * y for x, y in zip(self.a, other.a)) % MOD

class Matrix:
    def __init__(self, a):
        self.a = a

    def __add__(self, other):
        if isinstance(other, Vec):
            result = [0] * len(self.a)
            for i in range(len(self.a)):
                for j in range(i + 1):
                    result[i] += self.a[i][j] * other.a[j]
                result[i] %= MOD
            return Vec(result)
        result = [[0] * len(self.a) for _ in range(len(self.a))]
        for i in range(len(self.a)):
            for j in range(i + 1):
                for k in range(j, i + 1):
                    result[i][j] += self.a[i][k] * other.a[k][j]
                result[i][j] %= MOD
        return Matrix(result)

node = [
    Matrix([
        [1, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 0],
        [1, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [0, 0, 0, 1, 1, 0],
        [0, 0, 0, 1, 1, 1],
    ]),
    Matrix([
        [1, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [1, 1, 0, 1, 0, 0],
        [0, 0, 1, 0, 1, 0],
        [0, 0, 1, 0, 1, 1],
    ])
]

identity = Matrix([
    [1, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
])


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] - 1
        s_seq[i] = 1 - s_seq[i]
        st.update(i, node[s_seq[i]])
    else:
        l, r = args
        ans = st.query(l - 1, r, Vec([0, 0, 0, 0, 0, 1]), Vec([1, 0, 0, 0, 0, 0]))
        print(ans)
0