結果
| 問題 | No.426 往復漸化式 |
| ユーザー |
 shotoyoo
|
| 提出日時 | 2021-06-30 23:17:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 2,095 ms / 5,000 ms |
| コード長 | 6,273 bytes |
| コンパイル時間 | 1,315 ms |
| コンパイル使用メモリ | 87,128 KB |
| 実行使用メモリ | 309,740 KB |
| 最終ジャッジ日時 | 2023-09-09 16:22:25 |
| 合計ジャッジ時間 | 30,263 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 73 ms
71,424 KB |
| testcase_01 | AC | 130 ms
77,560 KB |
| testcase_02 | AC | 128 ms
77,612 KB |
| testcase_03 | AC | 308 ms
83,088 KB |
| testcase_04 | AC | 312 ms
84,772 KB |
| testcase_05 | AC | 782 ms
119,608 KB |
| testcase_06 | AC | 806 ms
117,848 KB |
| testcase_07 | AC | 1,633 ms
268,040 KB |
| testcase_08 | AC | 1,563 ms
267,808 KB |
| testcase_09 | AC | 2,041 ms
274,220 KB |
| testcase_10 | AC | 2,033 ms
273,060 KB |
| testcase_11 | AC | 1,215 ms
242,572 KB |
| testcase_12 | AC | 1,479 ms
243,924 KB |
| testcase_13 | AC | 1,937 ms
270,812 KB |
| testcase_14 | AC | 1,504 ms
246,656 KB |
| testcase_15 | AC | 1,175 ms
245,140 KB |
| testcase_16 | AC | 1,434 ms
244,128 KB |
| testcase_17 | AC | 1,571 ms
244,920 KB |
| testcase_18 | AC | 1,483 ms
244,408 KB |
| testcase_19 | AC | 1,126 ms
241,296 KB |
| testcase_20 | AC | 1,372 ms
242,648 KB |
| testcase_21 | AC | 2,095 ms
309,740 KB |
| testcase_22 | AC | 1,417 ms
242,704 KB |
ソースコード
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
def add(a,b):
n = len(a)
m = len(a[0])
res = [[(a[i][j] + b[i][j])%M for j in range(m)] for i in range(n)]
return res
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 = mul(B1, B2)
#nP = add(mul(B1, mul(P2, X1)), P1)
nP = add(mul(B1, mul(P2, X1)), P1)
nX = mul(X2, X1)
return (nB, nP, nX)
I2 = [[1,0],[0,1]]
I3 = [[1,0,0],[0,1,0],[0,0,1]]
ninf = None
n = int(input())
a0 = list(map(int, input().split()))
bn = list(map(int, input().split()))
q = int(input())
M = 10**9+7
l = []
flist = []
for i in range(n+1):
ii = 6*i
fi = [[ii, ii+1, ii+2], [ii+3, ii+4, ii+5]]
flist.append(fi)
l.append((I2, fi, I3))
l0 = [[item[:] 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 = list(map(int, t[2:]))
aa = [aa[:3], aa[3:6], aa[6:]]
l0[i][2] = aa
sg.update(i, l0[i][:])
elif t[0]=="b":
i = int(t[1])
bb = list(map(int, t[2:]))
bb = [bb[:2], bb[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 = mul2(res[0], bn)
bb1 = mul2(mul(res[1], res0[2]) , a0)
val = add([bb0], [bb1])[0]
write(" ".join(map(str, val)))