#1178637 (PyPy3) No.3492 区間冪乗加算一点取得

• 問題: No.3492 区間冪乗加算一点取得
• ユーザー: LyricalMaestro
• 提出日時: 2026-08-23 23:39:31
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 950 ms / 4,000 ms
• コード長: 5,765 bytes
• コンパイル時間: 670 ms
• コンパイル使用メモリ: 96,232 KB
• 実行使用メモリ: 118,428 KB
• 最終ジャッジ日時: 2026-08-23 23:39:46
• 合計ジャッジ時間: 13,299 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
other	AC * 27

ソースコード

# https://yukicoder.me/problems/no/3492

import math

MIN_VALUE = - 10 ** 18


class CombinationCalculator:
    """
    modを考慮したPermutation, Combinationを計算するためのクラス
    """    
    def __init__(self, size, mod):
        self.mod = mod
        self.factorial = [0] * (size + 1)
        self.factorial[0] = 1
        for i in range(1, size + 1):
            self.factorial[i] = (i * self.factorial[i - 1]) % self.mod
        
        self.inv_factorial = [0] * (size + 1)
        self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod)

        for i in reversed(range(size)):
            self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod

    def calc_combination(self, n, r):
        if n < 0 or n < r or r < 0:
            return 0

        if r == 0 or n == r:
            return 1
        
        ans = self.inv_factorial[n - r] * self.inv_factorial[r]
        ans %= self.mod
        ans *= self.factorial[n]
        ans %= self.mod
        return ans
    
    def calc_permutation(self, n, r):
        if n < 0 or n < r:
            return 0

        ans = self.inv_factorial[n - r]
        ans *= self.factorial[n]
        ans %= self.mod
        return ans
        

class LazySegmentTree:
    """
    非再帰版遅延セグメント木。
    更新は「加法」、取得は「最大値」のもの限定。
    取得のところの都合で取得演算子は可換になっている必要がある。
    """

    def __init__(self, init_array, max_degree, B):
        n = 1
        while n < len(init_array):
            n *= 2

        self.B = B
        self.max_degree = max_degree
        self.size = n
        self.array = [MIN_VALUE for _ in range(2 * self.size)]
        self.lazy_array = [[0] * (max_degree + 1) for _ in range(2 * self.size)]
        for i, a in enumerate(init_array):
            self.array[self.size + i] = a
    
    def _propagates(self, *ids):
        for i in reversed(ids):
            self._propagate(i)

    def _propagate(self, i):
        v = self.lazy_array[i]
        if self._is_zero(v):
            return
        
        if i < self.size:
            for j in range(self.max_degree + 1):
                self.lazy_array[2 * i][j] += v[j]
                self.lazy_array[2 * i][j] %= self.B
                self.lazy_array[2 * i + 1][j] += v[j]
                self.lazy_array[2 * i + 1][j] %= self.B

            self._addapt(2 * i, v)
            self._addapt(2 * i + 1, v)

        for j in range(self.max_degree + 1):
            self.lazy_array[i][j] = 0

    def _is_zero(self, v):
        for j in range(self.max_degree + 1):
            if v[j] != 0:
                return False
        return True

    def _addapt(self, index, v):
        if index >= self.size:
            i = index - self.size
            ans = 0
            for j in range(self.max_degree + 1):
                x = pow(i + 1, j, self.B)
                x *= v[j]
                x %= self.B
                ans += x
                ans %= self.B
            self.array[index] += ans
            self.array[index] %= self.B


    def _get_target_index(self, l, r):
        L = l + self.size; R = r + self.size
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while 0 < L and L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L > 0:
            yield L
            L >>= 1

    def add(self, l, r, v):
        # 2. 区間[l, r)のdata, lazyの値を更新
        L = self.size + l; R = self.size + r
        *ids, = self._get_target_index(l, r)
        self._propagates(*ids)
        while L < R:
            if R & 1:
                R -= 1
                for j in range(self.max_degree + 1):
                    self.lazy_array[R][j] += v[j]
                    self.lazy_array[R][j] %= self.B
                self._addapt(R, v)                

            if L & 1:
                for j in range(self.max_degree + 1):
                    self.lazy_array[L][j] += v[j]
                    self.lazy_array[L][j] %= self.B
                self._addapt(L, v)                
                L += 1
            L >>= 1; R >>= 1

        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する

    def get_value(self, m):
        # 1. トップダウンにlazyの値を伝搬
        self._propagates(*self._get_target_index(m, m + 1))
        return self.array[self.size + m]



def main():
    N, B, Q = map(int ,input().split())
    queries = []
    max_degree = 0
    for _ in range(Q):
        l, m, r, c, d = map(int, input().split())
        queries.append((l - 1, m - 1, r - 1, c, d))
        max_degree = max(max_degree, d)

    combi_map = {}
    def dfs(combi_map, d, j):
        if (d, j) in combi_map:
            return combi_map[(d, j)]

        if d == j or j == 0:
            x = 1
        elif d < 0 or d < j:
            x = 0
        else:
            x = dfs(combi_map, d - 1, j) + dfs(combi_map, d - 1, j - 1)
        combi_map[(d, j)] = x
        return x

    for d in range(max_degree + 1):
        for j in range(d + 1):
            dfs(combi_map, d, j)

    lazy_seg_tree = LazySegmentTree([0] * N, max_degree, B)
    for l, m, r, c, d in queries:
        v = [0] * (max_degree + 1)
        c %= B
        if c == 0:
            v[d] = 1
        else:
            for j in range(d + 1):
                x = combi_map[(d, j)]
                x *= pow(c, d - j, B)
                x %= B
                v[j] = x
        lazy_seg_tree.add(l, r + 1, v)

        ans = lazy_seg_tree.get_value(m)
        print(ans)


    




    





if __name__ == "__main__":
    main()