結果

問題 No.426 往復漸化式
ユーザー shotoyooshotoyoo
提出日時 2021-06-30 23:26:02
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 6,238 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 13,568 KB
実行使用メモリ 206,212 KB
最終ジャッジ日時 2024-06-27 09:17:23
合計ジャッジ時間 42,211 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 481 ms
44,552 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 3,781 ms
204,696 KB
testcase_12 AC 4,951 ms
204,296 KB
testcase_13 TLE -
testcase_14 AC 4,963 ms
204,304 KB
testcase_15 AC 3,852 ms
204,544 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 AC 3,739 ms
204,560 KB
testcase_20 AC 4,940 ms
204,808 KB
testcase_21 TLE -
testcase_22 AC 4,842 ms
204,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))

### セグメント木(はやい)
class SG:
    def __init__(self, n, v=None):
        self._n = n
        self.geta = 0
        x = 0
        while (1 << x) < n:
            x += 1
        self._log = x
        self._size = 1 << self._log
        self._d = [ninf] * (2 * self._size)
        if v is not None:
            for i in range(self._n):
                self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)
    def _update(self, k):
        self._d[k] = op(self._d[2 * k], self._d[2 * k + 1])
    def update(self, p, x):
        assert 0 <= p < self._n
#         x -= self.geta
        p += self._size
        self._d[p] = x
        for i in range(1, self._log + 1):
#             self._update(p >> i)
            k = p>>i
            self._d[k] = op(self._d[2 * k], self._d[2 * k + 1])
    def get(self, p):
        assert 0 <= p < self._n
        return self._d[p + self._size] # + self.geta
    def check(self):
        return [self.get(p) for p in range(self._n)]
    def query(self, left, right):
        # [l,r)の総和
        assert 0 <= left <= right <= self._n
        sml = ninf
        smr = ninf
        left += self._size
        right += self._size
        # 外側から計算していく(lは小さい側から, rは大きい側から)
        while left < right:
            if left & 1:
                sml = op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = op(self._d[right], smr)
            left >>= 1
            right >>= 1
        return op(sml, smr) # + self.geta
#     def update_all(self, v):
#         # 全体加算
#         self.geta += v
    def query_all(self):
        return self._d[1] # + self.geta
    def max_right(self, left, f):
        """f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最大の r
        -> rはf(op(a[l:r+1]))がFalseになる最小のr
        """
#         assert 0 <= left <= self._n
#         assert f(ninf)
        if left == self._n:
            return self._n
        left += self._size
        sm = ninf
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not f(op(sm, self._d[left])):
                while left < self._size:
                    left *= 2
                    if f(op(sm, self._d[left])):
                        sm = op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = op(sm, self._d[left])
            left += 1
        return self._n
    def min_left(self, right, f):
        """f(op(a[l], a[l + 1], ..., a[r - 1])) = true となる最小の l
        """
#         assert 0 <= right <= self._n
#         assert f(ninf)
        if right == 0:
            return 0
        right += self._size
        sm = ninf
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not f(op(self._d[right], sm)):
                while right < self._size:
                    right = 2 * right + 1
                    if f(op(self._d[right], sm)):
                        sm = op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = op(self._d[right], sm)
        return 0
def mul(a,b):
    """行列a,bの積
    aかbがNone のとき、単位行列として扱う
    """
    if a is None:
        return b
    elif b is None:
        return a
    n,m = len(a), len(a[0])
    k,l = len(b), len(b[0])
    # k==m
    out = [[0]*l for _ in range(n)]
    for i in range(n):
        for j in range(l):
            for p in range(m):
                out[i][j] += a[i][p]*b[p][j]%M
                if out[i][j]>M:
                    out[i][j] -= M
    return out
def mul2(m,a):
    """行列と配列の積
    m : None のとき単位行列扱い
    """
    if m is None:
        return a
    k,l = len(m), len(m[0])
#     ll = len(a)
    ans = [0]*k
    for i in range(k):
        for j in range(l):
            ans[i] += m[i][j] * a[j] % M
            if ans[i] > M:
                ans[i] -= M
    return ans

import numpy as np
def op(item1, item2):
    if item1 is None:
        return item2
    elif item2 is None:
        return item1
    B1, P1, X1 = item1
    B2, P2, X2 = item2
    nB = B1.dot(B2) % M
    nP = (P1 + B1.dot(P2.dot(X1))%M) % M
    nX = X2.dot(X1) % M
    return (nB, nP, nX)
from numpy import int64 as i64
I2 = np.eye(2, dtype=i64)
I3 = np.eye(3, dtype=i64)
ninf = None
n = int(input())
a0 = np.array(list(map(int, input().split())), dtype=i64)
bn = np.array(list(map(int, input().split())), dtype=i64)
q = int(input())
M = 10**9+7
l = []
flist = []
for i in range(n+1):
    ii = 6*i
    fi = np.array([[ii, ii+1, ii+2], [ii+3, ii+4, ii+5]], dtype=i64)
    flist.append(fi)
    l.append((I2, fi, I3))
l0 = [[np.array(item, dtype=i64) for item in v] for v in l]
sg = SG(n+1, l)
for _ in range(q):
    t = input().split()
    if t[0]=="a":
        i = int(t[1])
        aa = np.array(list(map(int, t[2:])), dtype=i64).reshape(3,3)
        l0[i][2] = aa
        sg.update(i, l0[i][:])
    elif t[0]=="b":
        i = int(t[1])
        bb = np.array(list(map(int, t[2:])), dtype=i64).reshape(2,2)
        l0[i][0] = bb
        sg.update(i, l0[i][:])
    elif t[0]=="ga":
        i = int(t[1])
        if i==0:
            val = a0
        else:
            res = sg.query(0, i)
            val = mul2(res[2], a0)
        write(" ".join(map(str, val)))
    elif t[0]=="gb":
        i = int(t[1])
        if i==n:
            val = bn
        else:
            res0 = sg.query(0, i+1)
            res = sg.query(i+1, n+1)
            bb0 = res[0].dot(bn) % M
            bb1 = ((res[1] @ res0[2]) % M) @ a0 % M
            val = (bb0 + bb1) % M
        write(" ".join(map(str, val)))
0