結果
| 問題 | No.3439 [Cherry 8th Tune] どの頂点にいた頃に戻りたいのか? |
| コンテスト | |
| ユーザー |
👑  Kazun
|
| 提出日時 | 2026-01-18 10:23:16 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 5,453 ms / 6,000 ms |
| コード長 | 36,708 bytes |
| 記録 | |
| コンパイル時間 | 479 ms |
| コンパイル使用メモリ | 82,988 KB |
| 実行使用メモリ | 269,576 KB |
| 最終ジャッジ日時 | 2026-01-23 21:06:52 |
| 合計ジャッジ時間 | 116,206 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 37 |
ソースコード
class Modulo_Polynomial:
__slots__= ("poly", "max_degree")
def __init__(self, poly: list[int] = None, max_degree: int = 2 * 10 ** 5):
""" 多項式を定義する (各係数の法 Mod はグローバル変数から指定する).
Args:
poly (list[int], optional): 係数のリスト. 第 d 要素は d 次の係数を表す. None のときは [0] と同義. Defaults to None.
max_degree (int, optional): (mod X^n) を考えるときの n. Defaults to 2*10**5.
"""
if poly is None:
poly = [0]
self.poly: list[int] = [a % Mod for a in poly[:max_degree]]
self.max_degree = max_degree
def __str__(self) -> str:
return str(self.poly)
def __repr__(self) -> str:
return f"{self.__class__.__name__}({self.poly})"
def __iter__(self):
yield from self.poly
def __eq__(self, other: "Modulo_Polynomial") -> bool:
from itertools import zip_longest
return all([a == b for a, b in zip_longest(self.poly, other.poly, fillvalue = 0)])
#+,-
def __pos__(self) -> "Modulo_Polynomial":
return self
def __neg__(self) -> "Modulo_Polynomial":
return self.scale(-1)
#items
def __getitem__(self, index):
if isinstance(index, slice):
return Modulo_Polynomial(self.poly[index], self.max_degree)
else:
if index<0:
raise IndexError(f"index is negative (index: {index})")
elif index>=len(self.poly):
return 0
else:
return self.poly[index]
def __setitem__(self, index, value):
if index<0:
raise IndexError(f"index is negative (index: {index})")
elif index>=self.max_degree:
return
if index>=len(self.poly):
self.poly+=[0]*(index-len(self.poly)+1)
self.poly[index]=value%Mod
#Boole
def __bool__(self) -> bool:
return any(self.poly)
#簡略化
def reduce(self):
""" 先頭の 0 を削除する.
"""
poly = self.poly
while poly and (poly[-1] == 0):
poly.pop()
#シフト
def __lshift__(self, depth: int) -> "Modulo_Polynomial":
if depth < 0:
return self >> (-depth)
if depth > self.max_degree:
return Modulo_Polynomial([0], self.max_degree)
return Modulo_Polynomial([0] * depth + self.poly, self.max_degree)
def __rshift__(self, depth: int) -> "Modulo_Polynomial":
if depth < 0:
return self << (-depth)
return Modulo_Polynomial(self.poly[depth:], self.max_degree)
#次数
def degree(self) -> int:
""" この多項式の次数を求める.
Returns:
int: 次数 (係数が 0 ではない最大次数)
"""
for d in range(len(self.poly) - 1, -1, -1):
if self.poly[d]:
return d
else:
return -float("inf")
#加法
def __add__(self, other) -> "Modulo_Polynomial":
P=self; Q=other
if Q.__class__==Modulo_Polynomial:
N=min(P.max_degree,Q.max_degree)
A=P.poly; B=Q.poly
else:
N=P.max_degree
A=P.poly; B=Q
return Modulo_Polynomial(Calc.add(A, B), N)
def __radd__(self, other) -> "Modulo_Polynomial":
return self+other
#減法
def __sub__(self, other) -> "Modulo_Polynomial":
P=self; Q=other
if Q.__class__==Modulo_Polynomial:
N=min(P.max_degree,Q.max_degree)
A=P.poly; B=Q.poly
else:
N=P.max_degree
A=P.poly; B=Q
return Modulo_Polynomial(Calc.sub(A, B), N)
def __rsub__(self, other) -> "Modulo_Polynomial":
return (-self) + other
#乗法
def __mul__(self, other) -> "Modulo_Polynomial":
P=self
Q=other
if Q.__class__==Modulo_Polynomial:
a=b=0
for x in P.poly:
if x:
a+=1
for y in Q.poly:
if y:
b+=1
if a>b:
P,Q=Q,P
P.reduce();Q.reduce()
U,V=P.poly,Q.poly
M=min(P.max_degree,Q.max_degree)
if a<2*P.max_degree.bit_length():
B=[0]*(len(U)+len(V)-1)
for i in range(len(U)):
if U[i]:
for j in range(len(V)):
B[i+j]+=U[i]*V[j]
if B[i+j]>Mod:
B[i+j]-=Mod
else:
B=Calc.convolution(U,V)[:M]
B=Modulo_Polynomial(B,M)
B.reduce()
return B
else:
return self.scale(other)
def __rmul__(self, other) -> "Modulo_Polynomial":
return self.scale(other)
#除法
def __floordiv__(self, other) -> "Modulo_Polynomial":
if not other:
raise ZeroDivisionError
if isinstance(other,int):
return self/other
self.reduce()
other.reduce()
return Modulo_Polynomial(Calc.flood_div(self.poly, other.poly), max(self.max_degree, other.max_degree))
def __rfloordiv__(self, other) -> "Modulo_Polynomial":
if not self:
raise ZeroDivisionError
if isinstance(other,int):
return Modulo_Polynomial([],self.max_degree)
#剰余
def __mod__(self, other) -> "Modulo_Polynomial":
if not other:
return ZeroDivisionError
self.reduce(); other.reduce()
r = Modulo_Polynomial(Calc.mod(self.poly, other.poly), min(self.max_degree, other.max_degree))
r.reduce()
return r
def __rmod__(self, other) -> "Modulo_Polynomial":
if not self:
raise ZeroDivisionError
r=other-(other//self)*self
r.reduce()
return r
def __divmod__(self, other) -> tuple["Modulo_Polynomial", "Modulo_Polynomial"]:
q=self//other
r=self-q*other; r.reduce()
return (q,r)
#累乗
def __pow__(self, other) -> "Modulo_Polynomial":
if other.__class__==int:
n=other
m=abs(n)
Q=self
A=Modulo_Polynomial([1],self.max_degree)
while m>0:
if m&1:
A*=Q
m>>=1
Q*=Q
if n>=0:
return A
else:
return A.inverse()
else:
P=Log(self)
return Exp(P*other)
def inverse(self, deg: int = None) -> "Modulo_Polynomial":
""" この多項式の (mod X^d) での逆元を求める.
Args:
deg (int, optional): 逆元の精度 ((mod X^d) の逆元を求める際の d) を指定する. None のときは元の多項式の精度をそのまま採用. Defaults to None.
Returns:
Modulo_Polynomial: _description_
"""
assert self.poly[0], "定数項が0"
if deg is None:
deg = self.max_degree
return Modulo_Polynomial(Calc.inverse(self.poly, deg), self.max_degree)
#除法
def __truediv__(self, other) -> "Modulo_Polynomial":
if isinstance(other, Modulo_Polynomial):
if Calc.is_sparse(other.poly):
d,f=Calc.coefficients_list(other.poly)
K=len(d)
H=[0]*self.max_degree
alpha=pow(other[0], -1, Mod)
H[0]=alpha*self[0]%Mod
for i in range(1, self.max_degree):
c=0
for j in range(1, K):
if d[j]<=i:
c+=f[j]*H[i-d[j]]%Mod
else:
break
c%=Mod
H[i]=alpha*(self[i]-c)%Mod
H=Modulo_Polynomial(H, min(self.max_degree, other.max_degree))
return H
else:
return self*other.inverse()
else:
return pow(other, -1, Mod)*self
def __rtruediv__(self, other: "Modulo_Polynomial") -> "Modulo_Polynomial":
return other*self.inverse()
#スカラー倍
def scale(self, s: int) -> "Modulo_Polynomial":
""" 多項式に s 倍を掛けた多項式を求める.
Args:
s (int): スカラー倍の係数
Returns:
Modulo_Polynomial: s 倍した多項式
"""
return Modulo_Polynomial(Calc.times(self.poly,s), self.max_degree)
#最高次の係数
def leading_coefficient(self) -> int:
""" 最高次の係数を求める
Returns:
int: 最高次の係数 (0 多項式の返り値は 0 とする)
"""
for a in self.poly[::-1]:
if a:
return a
else:
return 0
def censor(self, m: int = None):
""" m 次以降の係数を切り捨てる.
Args:
m (int, optional): 切り捨てる精度. Defaults to None.
"""
if m is None:
m = self.max_degree
m = min(m, self.max_degree)
del self.poly[m:]
def resize(self, m: int):
""" この多項式の情報を持っている配列の長さを m にする (短い場合は末尾に 0 を追加し, 長い場合は m 次以上を切り捨てる).
Args:
m (int): 次数
"""
m = min(m, self.max_degree)
if len(self.poly) > m:
del self.poly[:m]
elif len(self.poly) < m:
self.poly.extend([0] * (m - len(self.poly)))
#代入
def substitution(self, a: int) -> int:
""" 多項式の変数に a を形式的に代入した式の値を求める.
Args:
a (int): 代入する値
Returns:
int: 式の値
"""
y = 0
a_pow = 1
for p in self.poly:
y += p * a_pow % Mod
a_pow = (a_pow * a) % Mod
return y % Mod
def order(self, default: int = None) -> int:
""" この形式的ベキ級数の位数 (係数が 0 でない次数のうちの最低次数) を求める.
Args:
default (int, optional): ゼロ多項式の返り値. Defaults to None.
Returns:
int: 位数
"""
for d in range(len(self.poly)):
if self.poly[d]:
return d
else:
return default
#=================================================
class Calculator:
def __init__(self):
self.primitive = self.__primitive_root()
self.__build_up()
def __primitive_root(self) -> int:
""" Mod の原始根を求める.
Returns:
int: Mod の原始根
"""
p = Mod
if p == 2:
return 1
if p == 998244353:
return 3
if p == 10**9 + 7:
return 5
if p == 163577857:
return 23
if p == 167772161:
return 3
if p == 469762049:
return 3
fac=[]
q=2
v=p-1
while v>=q*q:
e=0
while v%q==0:
e+=1
v//=q
if e>0:
fac.append(q)
q+=1
if v>1:
fac.append(v)
for g in range(2, p):
if pow(g, p-1, p) != 1:
return None
flag=True
for q in fac:
if pow(g, (p-1) // q, p) == 1:
flag = False
break
if flag:
return g
#参考元: https://judge.yosupo.jp/submission/72676
def __build_up(self):
rank2=(~(Mod-1) & ((Mod-1)-1)).bit_length()
root=[0]*(rank2+1); iroot=[0]*(rank2+1)
rate2=[0]*max(0, rank2-1); irate2=[0]*max(0, rank2-1)
rate3=[0]*max(0, rank2-2); irate3=[0]*max(0, rank2-2)
root[-1]=pow(self.primitive, (Mod-1)>>rank2, Mod)
iroot[-1]=pow(root[-1], -1, Mod)
for i in range(rank2)[::-1]:
root[i]=root[i+1]*root[i+1]%Mod
iroot[i]=iroot[i+1]*iroot[i+1]%Mod
prod=iprod=1
for i in range(rank2-1):
rate2[i]=root[i+2]*prod%Mod
irate2[i]=iroot[i+2]*prod%Mod
prod*=iroot[i+2]; prod%=Mod
iprod*=root[i+2]; iprod%=Mod
prod=iprod = 1
for i in range(rank2-2):
rate3[i]=root[i + 3]*prod%Mod
irate3[i]=iroot[i + 3]*iprod%Mod
prod*=iroot[i + 3]; prod%=Mod
iprod*=root[i + 3]; iprod%=Mod
self.root=root; self.iroot=iroot
self.rate2=rate2; self.irate2=irate2
self.rate3=rate3; self.irate3=irate3
def add(self, A: list[int] | int, B: list[int] | int) -> list[int]:
""" 必要ならば末尾に元を追加して, [A[i] + B[i]] を求める.
"""
if type(A) == list:
pass
elif type(A) == int:
A = [A]
else:
raise NotImplementedError
if type(B) == list:
pass
elif type(B) == int:
B = [B]
else:
raise NotImplementedError
m = min(len(A), len(B))
C = [(A[i] + B[i]) %Mod for i in range(m)]
C.extend(A[m:])
C.extend(B[m:])
return C
def sub(self, A: list[int] | int, B: list[int] | int) -> list[int]:
""" 必要ならば末尾に元を追加して, [A[i] - B[i]] を求める.
"""
if type(A) == list:
pass
elif type(A) == int:
A = [A]
else:
raise NotImplementedError
if type(B) == list:
pass
elif type(B) == int:
B = [B]
else:
raise NotImplementedError
m = min(len(A), len(B))
C = [(A[i] - B[i]) % Mod for i in range(m)]
C.extend(A[m:])
C.extend([-b % Mod for b in B[m:]])
return C
def times(self, A: list[int], k: int) -> list[int]:
""" [k * A[i]] を求める.
"""
return [k * a % Mod for a in A]
#参考元 https://judge.yosupo.jp/submission/72676
def ntt(self, A: list[int]):
""" A に Mod を法とする数論変換を施す
※ Mod はグローバル変数から指定
References:
https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
https://judge.yosupo.jp/submission/72676
"""
N=len(A)
H=(N-1).bit_length()
l=0
I=self.root[2]
rate2=self.rate2; rate3=self.rate3
while l<H:
if H-l==1:
p=1<<(H-l-1)
rot=1
for s in range(1<<l):
offset=s<<(H-l)
for i in range(p):
x=A[i+offset]; y=A[i+offset+p]*rot%Mod
A[i+offset]=(x+y)%Mod
A[i+offset+p]=(x-y)%Mod
if s+1!=1<<l:
rot*=rate2[(~s&-~s).bit_length()-1]
rot%=Mod
l+=1
else:
p=1<<(H-l-2)
rot=1
for s in range(1<<l):
rot2=rot*rot%Mod
rot3=rot2*rot%Mod
offset=s<<(H-l)
for i in range(p):
a0=A[i+offset]
a1=A[i+offset+p]*rot
a2=A[i+offset+2*p]*rot2
a3=A[i+offset+3*p]*rot3
alpha=(a1-a3)%Mod*I
A[i+offset]=(a0+a2+a1+a3)%Mod
A[i+offset+p]=(a0+a2-a1-a3)%Mod
A[i+offset+2*p]=(a0-a2+alpha)%Mod
A[i+offset+3*p]=(a0-a2-alpha)%Mod
if s+1!=1<<l:
rot*=rate3[(~s&-~s).bit_length()-1]
rot%=Mod
l+=2
#参考元 https://judge.yosupo.jp/submission/72676
def inverse_ntt(self, A):
""" A を Mod を法とする逆数論変換を施す
※ Mod はグローバル変数から指定
References:
https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp
https://judge.yosupo.jp/submission/72676
"""
N=len(A)
H=(N-1).bit_length()
l=H
J=self.iroot[2]
irate2=self.rate2; irate3=self.irate3
while l:
if l==1:
p=1<<(H-l)
irot=1
for s in range(1<<(l-1)):
offset=s<<(H-l+1)
for i in range(p):
x=A[i+offset]; y=A[i+offset+p]
A[i+offset]=(x+y)%Mod
A[i+offset+p]=(x-y)*irot%Mod
if s+1!=1<<(l-1):
irot*=irate2[(~s&-~s).bit_length()-1]
irot%=Mod
l-=1
else:
p=1<<(H-l)
irot=1
for s in range(1<<(l-2)):
irot2=irot*irot%Mod
irot3=irot2*irot%Mod
offset=s<<(H-l+2)
for i in range(p):
a0=A[i+offset]
a1=A[i+offset+p]
a2=A[i+offset+2*p]
a3=A[i+offset+3*p]
beta=(a2-a3)*J%Mod
A[i+offset]=(a0+a1+a2+a3)%Mod
A[i+offset+p]=(a0-a1+beta)*irot%Mod
A[i+offset+2*p]=(a0+a1-a2-a3)*irot2%Mod
A[i+offset+3*p]=(a0-a1-beta)*irot3%Mod
if s+1!=1<<(l-2):
irot*=irate3[(~s&-~s).bit_length()-1]
irot%=Mod
l-=2
N_inv=pow(N, -1, Mod)
for i in range(N):
A[i]=N_inv*A[i]%Mod
def non_zero_count(self, A: list[int]) -> int:
""" A にある非零要素の個数を求める.
Args:
A (list[int]):
Returns:
int: 非零要素の個数
"""
return len(A) - A.count(0)
def is_sparse(self, A: list[int], threshold: int = 25) -> bool:
"""A が疎かどうかを判定する.
Args:
A (list[int]):
threshold (int, optional): 非零要素の個数が threshold 以下ならば疎と判定する. Defaults to 25.
Returns:
bool: 疎?
"""
return self.non_zero_count(A) <= threshold
def coefficients_list(self, A: list[int]) -> tuple[list[int], list[int]]:
""" A にある非零要素のリストを求める.
Args:
A (list[int]):
Returns:
tuple[list[int], list[int]]: ([d[0], ..., d[k-1]], [f[0], ..., f[k-1]]) の形のリスト.
j = 0, 1, ..., k - 1 に対して, a[d[j]] = f[j] であることを意味する.
"""
f = []; d = []
for i in range(len(A)):
if A[i] == 0:
continue
d.append(i)
f.append(A[i])
return d, f
def convoluton_greedy(self, A: list[int], B: list[int]) -> list[int]:
""" 畳み込み積 A * B を愚直な方法で求める.
Args:
A (list[int]):
B (list[int]):
Returns:
list[int]: 畳み込み積 A * B
"""
if len(A) < len(B):
A, B = B, A
n = len(A)
m = len(B)
C = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
C[i + j] += A[i] * B[j] % Mod
for k in range(n + m - 1):
C[k] %= Mod
return C
def convolution(self, A: list[int], B: list[int]) -> list[int]:
""" 畳み込み積 A * B を求める.
Args:
A (list[int]):
B (list[int]):
Returns:
list[int]: 畳み込み積 A * B
"""
if (not A) or (not B):
return []
N=len(A)
M=len(B)
L=M+N-1
if min(N,M)<=50:
return self.convoluton_greedy(A, B)
H=L.bit_length()
K=1<<H
A=A+[0]*(K-N)
B=B+[0]*(K-M)
self.ntt(A)
self.ntt(B)
for i in range(K):
A[i]=A[i]*B[i]%Mod
self.inverse_ntt(A)
return A[:L]
def autocorrelation(self, A: list[int]) -> list[int]:
""" 自分自身との畳み込み積を求める.
Args:
A (list[int]):
Returns:
list[int]: 畳み込み積 A * A
"""
N=len(A)
L=2*N-1
if N<=50:
C=[0]*L
for i in range(N):
for j in range(N):
C[i+j]+=A[i]*A[j]
C[i+j]%=Mod
return C
H=L.bit_length()
K=1<<H
A=A+[0]*(K-N)
self.ntt(A)
for i in range(K):
A[i]=A[i]*A[i]%Mod
self.inverse_ntt(A)
return A[:L]
def multiple_convolution(self, *A: list[int]) -> list[int]:
""" A = (A[0], A[1], ..., A[k - 1]) に対して, この k 個の畳み込み積 A[0] * A[1] * ... * A[k - 1] を求める.
Args:
A (list[list[int]]): 畳み込む k 個の整数のリスト
Returns:
list[int]: k 個の畳み込み積 A[0] * A[1] * ... * A[k - 1]
"""
from collections import deque
if not A:
return [1]
Q=deque(list(range(len(A))))
A=list(A)
while len(Q)>=2:
i=Q.popleft(); j=Q.popleft()
A[i]=self.convolution(A[i], A[j])
A[j]=None
Q.append(i)
i=Q.popleft()
return A[i]
def inverse(self, F: list[int], length: int = None) -> list[int]:
""" F * G = [1, 0, 0, ..., 0] (0 が (length - 1) 個) を満たす長さ length のリスト G を求める.
Args:
F (list[int]):
length (int, optional): 求める G の長さ. None のときは length = len(F) とする. Defaults to None.
Returns:
list[int]: _description_
"""
M = len(F) if length is None else length
if M <= 0:
return []
if self.is_sparse(F):
# 愚直に漸化式を用いて求める.
# 計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間
d,f=self.coefficients_list(F)
G=[0]*M
alpha=pow(F[0], -1, Mod)
G[0]=alpha
for i in range(1, M):
for j in range(1, len(d)):
if d[j]<=i:
G[i]+=f[j]*G[i-d[j]]%Mod
else:
break
G[i]%=Mod
G[i]=(-alpha*G[i])%Mod
del G[M:]
else:
# FFTの理論を応用して求める.
# 計算量: 求めたい項の個数をNとして, O(N log N)
# Reference: https://judge.yosupo.jp/submission/42413
N=len(F)
r=pow(F[0], -1, Mod)
m=1
G=[r]
while m<M:
A=F[:min(N, 2*m)]; A+=[0]*(2*m-len(A))
B=G.copy(); B+=[0]*(2*m-len(B))
Calc.ntt(A); Calc.ntt(B)
for i in range(2*m):
A[i]=A[i]*B[i]%Mod
Calc.inverse_ntt(A)
A=A[m:]+[0]*m
Calc.ntt(A)
for i in range(2*m):
A[i]=-A[i]*B[i]%Mod
Calc.inverse_ntt(A)
G.extend(A[:m])
m<<=1
G=G[:M]
return G
def flood_div(self, F: list[int], G: list[int]) -> list[int]:
assert F[-1]
assert G[-1]
F_deg=len(F)-1
G_deg=len(G)-1
if F_deg<G_deg:
return []
m=F_deg-G_deg+1
return self.convolution(F[::-1], Calc.inverse(G[::-1],m))[m-1::-1]
def mod(self, F: list[int], G: list[int]) -> list[int]:
while F and F[-1] == 0:
F.pop()
while G and G[-1] == 0:
G.pop()
if not F:
return []
return Calc.sub(F, Calc.convolution(Calc.flood_div(F, G), G))
#==================================================
"""
Note
[1] RMQ(区間上の最小値:Range Minimum Query)
op=lambda x,y:min(x,y)
unit=float("inf")
act=lambda alpha,x:alpha
comp=lambda alpha,beta:alpha
"""
from typing import TypeVar, Callable, Generic
M = TypeVar('M')
F = TypeVar('F')
class Lazy_Evaluation_Tree(Generic[M, F]):
def __init__(self, L: list[M], op: Callable[[M, M], M], unit: M, act: Callable[[F, M], M], comp: Callable[[F, F], F], id: F):
""" op を演算, act を作用とする L を初期状態とする遅延セグメント木を作成する.
[条件]
M: Monoid, F={f: F x M→ M: 作用素} に対して, 以下が成立する.
F は恒等写像 id を含む.つまり, 任意の x in M に対して id(x)=x
F は写像の合成に閉じている. つまり, 任意の f,g in F に対して, comp(f,g) in F
任意の f in F, x,y in M に対して, f(xy)=f(x) f(y) である.
[注意]
作用素は左から掛ける. 更新も左から.
Args:
L (list[M]): 初期状態
op (Callable[[M, M], M]): M の演算
unit (M): M の単位元
act (Callable[[F, M], M]): F から M への作用
comp (Callable[[F, F], F]): F 同士の合成
id (F): F の単位元
"""
self.op = op
self.unit = unit
self.act = act
self.comp = comp
self.id = id
N = len(L)
d = max(1, (N - 1).bit_length())
k = 1 << d
self.data = data = [unit] * k + L + [unit] * (k - len(L))
self.lazy = [id] * (2 * k)
self.N = k
self.depth = d
for i in range(k - 1, 0, -1):
data[i] = op(data[i << 1], data[i << 1 | 1])
def _eval_at(self, m: int) -> None:
return self.data[m] if self.lazy[m] == self.id else self.act(self.lazy[m], self.data[m])
#配列の第m要素を下に伝搬
def _propagate_at(self, m: int) -> None:
self.data[m] = self._eval_at(m)
lazy = self.lazy; comp = self.comp
if m < self.N and self.lazy[m] != self.id:
lazy[m << 1] = comp(lazy[m], lazy[m << 1])
lazy[m << 1 | 1] = comp(lazy[m], lazy[m << 1 | 1])
lazy[m] = self.id
#配列の第m要素より上を全て伝搬
def _propagate_above(self, m: int) -> None:
for h in range(m.bit_length() - 1, 0, -1):
self._propagate_at(m >> h)
#配列の第m要素より上を全て再計算
def _recalc_above(self, m: int) -> None:
data = self.data; op = self.op
eval_at = self._eval_at
while m > 1:
m >>= 1
data[m] = op(eval_at(m << 1), eval_at(m << 1 | 1))
def get(self, k: int) -> M:
""" 第 k 要素を取得する
Args:
k (int): 要素の場所
Returns:
M: 第 k 要素
"""
m = k + self.N
self._propagate_above(m)
self.data[m] = self._eval_at(m)
self.lazy[m] = self.id
return self.data[m]
#作用
def action(self, l: int, r: int, alpha: F, left_closed: bool = True, right_closed: bool = True) -> None:
""" 第 l 要素から第 r 要素まで全てに alpha を作用させる
Args:
l (int): 左端
r (int): 右端
alpha (F): 作用させる値
left_closed (bool, optional): False にすると, 左端が開区間になる. Defaults to True.
right_closed (bool, optional): False にすると, 右端が開区間になる. Defaults to True.
"""
L = l + self.N + (not left_closed)
R = r + self.N + right_closed
L0 = R0 = -1
X, Y = L, R- 1
while X < Y:
if X & 1:
L0 = max(L0, X)
X += 1
if Y & 1 == 0:
R0 = max(R0, Y)
Y -= 1
X >>= 1
Y >>= 1
L0 = max(L0, X)
R0 = max(R0, Y)
self._propagate_above(L0)
self._propagate_above(R0)
lazy = self.lazy; comp = self.comp
while L < R:
if L & 1:
lazy[L] = comp(alpha, lazy[L])
L += 1
if R & 1:
R -= 1
lazy[R] = comp(alpha, lazy[R])
L >>= 1
R >>= 1
self._recalc_above(L0)
self._recalc_above(R0)
def update(self, k: int, x: M) -> None:
""" 第 k 要素を x に更新する.
Args:
k (int): 要素の場所
x (M): 変更後の第 k 要素
"""
m = k+self.N
self._propagate_above(m)
self.data[m] = x
self.lazy[m] = self.id
self._recalc_above(m)
def product(self, l: int, r: int, left_closed: bool = True, right_closed: bool = True) -> M:
""" 第 l 要素から第 r 要素までの総積を求める.
Args:
l (int): 左端
r (int): 右端
left_closed (bool, optional): False にすると, 左端が開区間になる. Defaults to True.
right_closed (bool, optional): False にすると, 右端が開区間になる. Defaults to True.
Returns:
M: 総積
"""
L = l + self.N + (not left_closed)
R = r + self.N + right_closed
L0 = R0 = -1
X, Y = L, R - 1
while X < Y:
if X & 1:
L0 = max(L0, X)
X += 1
if Y & 1 == 0:
R0 = max(R0, Y)
Y -= 1
X >>= 1
Y >>= 1
L0 = max(L0, X)
R0 = max(R0, Y)
self._propagate_above(L0)
self._propagate_above(R0)
vL = vR = self.unit
op = self.op; eval_at = self._eval_at
while L < R:
if L & 1:
vL = op(vL, eval_at(L))
L += 1
if R & 1:
R -= 1
vR = op(eval_at(R), vR)
L >>= 1
R >>= 1
return self.op(vL, vR)
def all_product(self) -> M:
""" この遅延セグメント木が持っている要素に関する総積を求める.
Returns:
M: 総積
"""
return self.product(0, self.N - 1)
def max_right(self, left: int, cond: Callable[[int], bool]) -> int:
""" 以下の2つをともに満たす r の1つを返す.\n
(1) r = left or cond(data[left] * data[left + 1] * ... * data[r - 1]): True
(2) r = N or cond(data[left] * data[left + 1] * ... * data[r]): False
※ cond が単調減少の時, cond(data[left] * ... * data[r - 1]): True を満たす最大の r となる.
Args:
left (int): 左端
cond: 条件式 (cond(unit) = True を要求)
Returns:
int: 条件を満たす r.
"""
assert 0 <= left <= self.N
assert cond(self.unit)
if left == self.N:
return self.N
left += self.N
def max_right(self, left: int, cond) -> int:
""" 以下の (1), (2) を満たす整数 r を求める.
(1) r=left or cond(data[left] data[left+1] ... data[r-1]): True
(2) r=N or cond(data[left] data[left+1] ... data[r]): False
Args:
left (int): 左端
cond : 条件
Returns:
int: (1), (2) を満たす整数 r
"""
assert 0 <= left <= self.N, f"添字 ({left = }) が範囲外"
assert cond(self.unit), "単位元が条件を満たさない"
if left == self.N:
return self.N
left += self.N
sm = self.unit
op = self.op; data = self.data
first = True
self._propagate_above(left)
while first or (left & (-left)) != left:
first = False
while left % 2 == 0:
left >>= 1
if not cond(op(sm, self._eval_at(left))):
while left < self.N:
self._propagate_at(left)
left <<= 1
self._propagate_at(left)
if cond(op(sm, data[left])):
sm = op(sm, data[left])
left += 1
return left - self.N
sm = op(sm, self._eval_at(left))
left += 1
return self.N
#リフレッシュ
def refresh(self) -> None:
""" 遅延セグメント木の遅延情報をリセットする.
"""
lazy = self.lazy; comp = self.comp
for m in range(1, 2 * self.N):
self.data[m] = self._eval_at(m)
if m < self.N and self.lazy[m] != self.id:
lazy[m << 1] = comp(lazy[m], lazy[m << 1])
lazy[m << 1 | 1] = comp(lazy[m], lazy[m << 1 | 1])
lazy[m] = self.id
def __getitem__(self, k: int) -> M:
return self.get(k)
def __setitem__(self, k: int, x: M) -> None:
self.update(k, x)
#==================================================
from operator import add
def encode(x0: int, x1: int) -> int:
return 1_000_000_000 * x0 + x1
def decode(y: int) -> tuple[int, int]:
return divmod(y, 1_000_000_000)
def act_1(a: int, x: int) -> int:
x0, x1 = decode(x)
return x if a % 2 == 0 else encode(x1, x0)
def act_2(a: int, y: int) -> int:
y0, y1 = decode(y)
return encode(y0 + a * y1, y1)
def solve():
N, Q = map(int, input().split())
S = list(f"*{input().strip()}")
S[-1] = "B"
W = list(map(int, input().split()))
X = Lazy_Evaluation_Tree[tuple[int, int], int](
[encode(1, 0) if S[i] in { "G", "*" } else encode(0, 1) for i in range(N + 1)],
add,
encode(0, 0),
act_1,
add,
0
)
W = Lazy_Evaluation_Tree[tuple[int, int], int](
[encode(w, 1) for w in W],
add,
encode(0, 0),
act_2,
add,
0
)
def latest_backed_at(v: int) -> int:
alpha = decode(X.product(1, v - 1))
if alpha[1] == 0:
return 0
return X.max_right(1, lambda z: decode(z)[1] < alpha[1])
def next_back_at(v: int) -> int:
beta = decode(X.product(1, v - 1))
return min(X.max_right(1, lambda z: decode(z)[1] <= beta[1]), N)
ans = []
for q in range(Q):
mode, *option = map(int, input().split())
if mode == 1:
l, r = option
if r == N:
r -= 1
X.action(l, r, 1)
elif mode == 2:
l, r, a = option
W.action(l, r, a)
elif mode == 3:
v, K = option
U = list(map(int, input().split()))
# U 以降 (U 含める) で最初の Back になる r を求める.
r = latest_backed_at(v)
back_time: defaultdict[int, int] = defaultdict(int)
less = 0
for u in U:
# v より前の頂点は, 絶対に子孫にならないので, SKIP
if u < v:
less += 1
continue
t = latest_backed_at(u)
back_time[t] += 1
vr = next_back_at(v)
p = decode(W.product(v, vr))[0] * pow(decode(W.product(0, vr))[0], -1, Mod) % Mod
polys = []
# 確定要素
poly = [1 if s == back_time[r] else 0 for s in range(back_time[r] + 1)] + [0] * less
polys.append(poly)
for t, d in back_time.items():
if t == r:
continue
poly = [0] * (d + 1)
poly[0] += 1 - p
poly[d] += p
polys.append(poly)
P = Calc.multiple_convolution(*polys)
ans.append(P)
return ans
#==================================================
import sys
input = sys.stdin.readline
write = sys.stdout.write
from collections import defaultdict
Mod = 998244353
Calc = Calculator()
to_string = lambda P: " ".join(map(str, P))
write("\n".join(map(to_string, solve())))