結果

問題 No.3110 WIP Editorial
ユーザー 👑 p-adicp-adic
提出日時 2024-03-09 20:27:55
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 14,186 bytes
コンパイル時間 130 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 45,588 KB
最終ジャッジ日時 2024-03-09 20:28:08
合計ジャッジ時間 13,289 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
11,392 KB
testcase_01 AC 3,203 ms
17,920 KB
testcase_02 TLE -
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#基点付きマグマ
class L:
	point=None
	def __init__(self,val):
		self.val = val
	def __eq__(self,other):
		return self.val==other.val
	def __imul__(self,other):
		self.val *= other.val #ユーザー定義
		return self
	def __mul__(self,other):
		return self.__class__(self.val*other.val) #ユーザー定義
	def copy(self):
		return self.__class__(self.val)
L.point=L(1) #ユーザー定義
# 区間作用を行わない場合もL.pointの作用を区間積に用いるため、
# Lをdummyにせず自明群{1}などを用いる必要があることに注意。

# Lの基点が恒等変換に対応する左L作用つきN加群
class M:
	one=None
	def __init__(self,val):
		self.val = val
	def __eq__(self,other):
		return self.val==other.val
	def __mul__(self,other):
		return self.__class__(self.val+other.val) #ユーザー定義
	def __pow__(self,n):
		return self.__class__(self.val*n) #ユーザー定義
	def __ixor__(self,x):
		self.val*=x.val #ユーザー定義
		return self
	def __xor__(self,x):
		return self.__class__(self.val*x.val) #ユーザー定義
	def copy(self):
		return self.__class__(self.val)
M.one=M(0) #ユーザー定義

# 配列による初期化O(N)

# 一点取得O(1)
# 区間積取得O(N^{1/2})（Mのモノイド性を使う）

# 一点代入O(N^{1/2})（MのN加群性を使う）
# 区間代入O(N^{1/2})（MのN加群性を使う）
# 一点乗算はなし。
# 区間乗算O(N^{1/2})（Mの可換性を使う）
# 一点作用はなし。
# 区間作用O(N^{1/2})
class IntervalMultiplyLazySqrtDecomposition:
	def __init__(self,a):
		self.N = len(a)
		self.N_sqrt = int( self.N**0.5 ) + 1
		self.N_d = ( self.N + self.N_sqrt - 1 ) // self.N_sqrt
		self.N_m = self.N_d * self.N_sqrt
		self.a = a[:]
		self.b = [M.one.copy()for d in R(self.N_d)]
		self.lazy_substitution = self.b[:]
		self.suspended = [False] * self.N_d
		self.lazy_action = [L.point.copy()for d in R(self.N_d)]
		self.lazy_multiplication = self.b[:]
		self.a += [M.one.copy()for d in R(self.N_m)]
		i_min = 0
		i_ulim = self.N_sqrt
		for d in R(self.N_d):
			for i in R(i_min,i_ulim):self.b[d] *= self.a[i]
			i_min = i_ulim
			i_ulim += self.N_sqrt

	def Set(self,i,u):
		d = i // self.N_sqrt
		i_min = d * self.N_sqrt
		i_ulim = i_min + self.N_sqrt
		if self.suspended[d]:
			if self.lazy_substitution[d] != u:
				SolveSuspendedSubstitution( d , self.lazy_substitution[d] )
				self.a[i] = u
				# N加群性を使った
				self.b[d] = ( self.lazy_substitution[d] ** self.N_sqrt - 1 ) * u
		else:
			self.SolveSuspendedAction( d )
			if self.a[i] != u:
				self.a[i] = u
				self.SetProduct( d )

	def IntervalSet(self,i_start,i_final,u):
		i_min = max( i_start , 0 )
		i_ulim = min( i_final + 1 , self.N )
		d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
		d_1 = max( d_0 , i_ulim // self.N_sqrt )
		d_0_N_sqrt = d_0 * self.N_sqrt
		d_1_N_sqrt = d_1 * self.N_sqrt
		i_0 = min( d_0_N_sqrt , i_ulim )
		i_1 = max( i_0 , d_1_N_sqrt )
		if i_min < i_0:
			# この時d_0 > 0になる。
			d_0_minus = d_0 - 1
			d_0_N_sqrt_minus = d_0_N_sqrt - self.N_sqrt
			if self.suspended[d_0_minus]:
				self.IntervalSet_Body( d_0_N_sqrt_minus , i_min , self.lazy_substitution[d_0_minus] )
				self.IntervalSet_Body( i_min , i_0 , u )
				self.IntervalSet_Body( i_0 , d_0_N_sqrt , self.lazy_substitution[d_0_minus] )
				self.suspended[d_0_minus] = False
				# N加群性を使った。
				self.b[d_0_minus] = self.lazy_substitution[d_0_minus] ** ( self.N_sqrt - ( i_0 - i_min ) ) * ( u ** ( i_0 - i_min ) )
			else:
				self.SolveSuspendedAction( d_0_minus )
				self.IntervalSet_Body( i_min , i_0 , u )
				self.b[d_0_minus] = ( self.IntervalProduct_Body( d_0_N_sqrt_minus , i_min ) * ( u ** ( i_0 - i_min ) ) ) * self.IntervalProduct_Body( i_0 , d_0_N_sqrt )
		power = u ** self.N_sqrt
		for d in R(d_0,d_1):
			self.b[d] = power
			self.lazy_substitution[d] = u
			self.suspended[d] = True
			self.lazy_multiplication[d] = M.one.copy()
			self.lazy_action[d] = L.point.copy()
		if i_1 < i_ulim:
			# この時d_1 < self.N_dになる。
			d_1_N_sqrt_plus = d_1_N_sqrt + self.N_sqrt
			self.b[d_1] = self.b[d_1]
			if self.suspended[d_1]:
				self.IntervalSet_Body( d_1_N_sqrt , i_1 , self.lazy_substitution[d_1] )
				self.IntervalSet_Body( i_1 , i_ulim , u )
				self.IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_substitution[d_1] )
				self.suspended[d_1] = False
				self.b[d_1] = ( self.lazy_substitution[d_1] ** ( i_1 - d_1_N_sqrt ) ) * ( u ** ( i_ulim - i_1 ) ) * ( self.lazy_substitution[d_1] ** ( d_1_N_sqrt_plus - i_ulim ) )
			else:
				self.SolveSuspendedAction( d_1 )
				self.IntervalSet_Body( i_1 , i_ulim , u )
				self.b[d_1] = ( self.IntervalProduct_Body( d_1_N_sqrt , i_1 ) * ( u ** ( i_ulim - i_1 ) ) ) * self.IntervalProduct_Body( i_ulim , d_1_N_sqrt_plus )

	def IntervalAct(self,i_start,i_final,r):
		if r != L.point:
			i_min = max( i_start , 0 )
			i_ulim = min( i_final + 1 , self.N )
			d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
			d_1 = max( d_0 , i_ulim // self.N_sqrt )
			d_0_N_sqrt = d_0 * self.N_sqrt
			d_1_N_sqrt = d_1 * self.N_sqrt
			i_0 = min( d_0_N_sqrt , i_ulim )
			i_1 = max( i_0 , d_1_N_sqrt )
			if i_min < i_0:
				# この時d_0 > 0になる。
				d_0_minus = d_0 - 1
				d_0_N_sqrt_minus = d_0_N_sqrt - self.N_sqrt;
				if self.suspended[d_0_minus]:
					u = self.lazy_substitution[d_0_minus] ^ r
					self.IntervalSet_Body( d_0_N_sqrt_minus , i_min , self.lazy_substitution[d_0_minus] )
					self.IntervalSet_Body( i_min , i_0 , u )
					self.IntervalSet_Body( i_0 , d_0_N_sqrt , self.lazy_substitution[d_0_minus] )
					self.suspended[d_0_minus] = False
					# N加群性を使った。
					self.b[d_0_minus] = ( self.lazy_substitution[d_0_minus] ** ( self.N_sqrt - ( i_0 - i_min ) ) ) * ( u ** ( i_0 - i_min ) )
				else:
					if self.lazy_action[d_0_minus] == L.point:self.IntervalAct_Body( i_min , i_0 , r )
					else:
						self.IntervalAct_Body( d_0_N_sqrt_minus , i_min , self.lazy_action[d_0_minus] )
						self.IntervalAct_Body( i_min , i_0 , r * self.lazy_action[d_0_minus] )
						self.IntervalAct_Body( i_0 , d_0_N_sqrt , self.lazy_action[d_0_minus] )
						self.lazy_action[d_0_minus] = L.point.copy()
					if self.lazy_multiplication[d_0_minus] != M.one:
						IntervalMultiply_Body( d_0_N_sqrt_minus , i_min , self.lazy_multiplication[d_0_minus] )
						IntervalMultiply_Body( i_min , i_0 , self.lazy_multiplication[d_0_minus] ^ r )
						IntervalMultiply_Body( i_0 , d_0_N_sqrt , self.lazy_multiplication[d_0_minus] )
						self.lazy_multiplication[d_0_minus] = M.one.copy()
					self.SetProduct( d_0_minus )
			for d in R(d_0,d_1):
				self.b[d] = self.b[d] ^ r
				if self.suspended[d]:self.lazy_substitution[d] ^= r
				else:
					self.lazy_action[d] ^= r
					self.lazy_multiplication[d] ^= r
			if i_1 < i_ulim:
				# この時d_1 < self.N_dになる。
				d_1_N_sqrt_plus = d_1_N_sqrt + self.N_sqrt
				if self.suspended[d_1]:
					u = self.lazy_substitution[d_1] ^ r
					self.IntervalSet_Body( d_1_N_sqrt , i_1 , self.lazy_substitution[d_1] )
					self.IntervalSet_Body( i_1 , i_ulim , u )
					self.IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_substitution[d_1] )
					self.suspended[d_1] = False
					# N加群性を使った。
					self.b[d_1] = ( self.lazy_substitution[d_1] ** ( self.N_sqrt - ( i_ulim - i_1 ) ) ) * ( u ** ( i_ulim - i_1 ) )
				else:
					if self.lazy_action[d_1] == L.point:self.IntervalAct_Body( i_1 , i_ulim , r )
					else:
						self.IntervalAct_Body( d_1_N_sqrt , i_1 , self.lazy_action[d_1] )
						self.IntervalAct_Body( i_1 , i_ulim , r * self.lazy_action[d_1] )
						self.IntervalAct_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_action[d_1] )
						self.lazy_action[d_1] = L.point.copy()
					if self.lazy_multiplication[d_1] != M.one:
						self.IntervalMultiply_Body( d_1_N_sqrt , i_1 , self.lazy_multiplication[d_1] )
						self.IntervalMultiply_Body( i_1 , i_ulim , self.lazy_multiplication[d_1] ^ r )
						self.IntervalMultiply_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_multiplication[d_1] )
						self.lazy_multiplication[d_1] = M.one.copy()
					self.SetProduct( d_1 )

	def IntervalMultiply(self,i_start,i_final,u):
		if u != M.one:
			i_min = max( i_start , 0 )
			i_ulim = min( i_final + 1 , self.N )
			d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
			d_1 = max( d_0 , i_ulim // self.N_sqrt )
			d_0_N_sqrt = d_0 * self.N_sqrt
			d_1_N_sqrt = d_1 * self.N_sqrt
			i_0 = min( d_0_N_sqrt , i_ulim )
			i_1 = max( i_0 , d_1_N_sqrt )
			if i_min < i_0:
				# この時d_0 > 0になる。
				d_0_minus = d_0 - 1
				d_0_N_sqrt_minus = d_0_N_sqrt - self.N_sqrt
				# N加群性を使った。
				self.b[d_0_minus] *= u ** ( i_0 - i_min )
				if self.suspended[d_0_minus]:
					self.IntervalSet_Body( d_0_N_sqrt_minus , i_min , self.lazy_substitution[d_0_minus] )
					self.IntervalSet_Body( i_min , i_0 , self.lazy_substitution[d_0_minus] * u )
					self.IntervalSet_Body( i_0 , d_0_N_sqrt , self.lazy_substitution[d_0_minus] )
					self.suspended[d_0_minus] = False
				else:
					if self.lazy_action[d_0_minus] != L.point:
						self.IntervalAct_Body( d_0_N_sqrt_minus , d_0_N_sqrt , self.lazy_action[d_0_minus] )
						self.lazy_action[d_0_minus] = L.point.copy()
					if self.lazy_multiplication[d_0_minus] == M.one:self.IntervalMultiply_Body( i_min , i_0 , u )
					else:
						self.IntervalMultiply_Body( d_0_N_sqrt_minus , i_min , self.lazy_multiplication[d_0_minus] )
						self.IntervalMultiply_Body( i_min , i_0 , self.lazy_multiplication[d_0_minus] * u )
						self.IntervalMultiply_Body( i_0 , d_0_N_sqrt , self.lazy_multiplication[d_0_minus] )
						self.lazy_multiplication[d_0_minus] = M.one.copy()
			power = u ** self.N_sqrt
			for d in R(d_0,d_1):
				# N加群性を使った。
				self.b[d] *= power
				if self.suspended[d]:self.lazy_substitution[d] *= u
				else:self.lazy_multiplication[d] *= u
			if i_1 < i_ulim:
				# この時d_1 < self.N_dになる。
				d_1_N_sqrt_plus = d_1_N_sqrt + self.N_sqrt
				# N加群性を使った。
				self.b[d_1] *= u ** ( i_ulim - i_1 )
				if self.suspended[d_1]:
					self.IntervalSet_Body( d_1_N_sqrt , i_1 , self.lazy_substitution[d_1] )
					self.IntervalSet_Body( i_1 , i_ulim , self.lazy_substitution[d_1] * u )
					self.IntervalSet_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_substitution[d_1] )
					self.suspended[d_1] = False
				else:
					if self.lazy_action[d_1] != L.point:
						self.IntervalAct_Body( d_1_N_sqrt , d_1_N_sqrt_plus , self.lazy_action[d_1] )
						self.lazy_action[d_1] = L.point.copy()
					if self.lazy_multiplication[d_1] == M.one:self.IntervalMultiply_Body( i_1 , i_ulim , u )
					else:
						self.IntervalMultiply_Body( d_1_N_sqrt , i_1 , self.lazy_multiplication[d_1] )
						self.IntervalMultiply_Body( i_1 , i_ulim , self.lazy_multiplication[d_1] * u )
						self.IntervalMultiply_Body( i_ulim , d_1_N_sqrt_plus , self.lazy_multiplication[d_1] )
						self.lazy_multiplication[d_1] = M.one.copy()

	def Get(self,i):
		d = i // self.N_sqrt
		return self.lazy_substitution[d] if self.suspended[d]else ( self.a[i] ^ self.lazy_action[d] ) * self.lazy_multiplication[d]

	def IntervalProduct(self,i_start,i_final):
		i_min = max( i_start , 0 )
		i_ulim = min( i_final + 1 , self.N )
		d_0 = ( i_min + self.N_sqrt - 1 ) // self.N_sqrt
		d_1 = max( d_0 , i_ulim // self.N_sqrt )
		i_0 = min( d_0 * self.N_sqrt , i_ulim )
		i_1 = max( i_0 , d_1 * self.N_sqrt )
		answer = M.one.copy()
		if i_min < i_0:
			# この時d_0 > 0になる。
			# N加群性を使った。
			d_0_minus = d_0 - 1
			answer = ( self.lazy_substitution[d_0_minus] ** ( i_0 - i_min ) )if self.suspended[d_0_minus]else( ( self.IntervalProduct_Body( i_min , i_0 ) ^ self.lazy_action[d_0_minus] ) * ( self.lazy_multiplication[d_0_minus] ** ( i_0 - i_min ) ) )
		for d in R(d_0,d_1):answer *= self.b[d]
		if i_1 < i_ulim:
			# この時d_1 < self.N_dになる。
			# N加群性を使った。
			answer *= ( self.lazy_substitution[d_1] ** ( i_ulim - i_1 ) )if self.suspended[d_1]else( ( self.IntervalProduct_Body( i_1 , i_ulim ) ^ self.lazy_action[d_1] ) * ( self.lazy_multiplication[d_1] ** ( i_ulim - i_1 ) ) )
		return answer

	#private:
	def SetProduct(self,i):
		self.b[d] = M.one.copy()
		i_min = d * self.N_sqrt
		i_ulim = i_min + self.N_sqrt
		for i in R(i_min,i_ulim):self.b[d] *= self.a[i]

	def SolveSuspendedSubstitution(self,d,u):
		i_min = d * self.N_sqrt
		self.IntervalSet_Body( i_min , i_min + self.N_sqrt , u )
		self.suspended[d] = False

	def IntervalSet_Body(self,i_min,i_ulim,u):
		for i in R(i_min,i_ulim):self.a[i] = u

	def SolveSuspendedAction(self,d):
		i_min = d * self.N_sqrt
		i_ulim = i_min + self.N_sqrt
		if self.lazy_action[d] != L.point:
			self.IntervalAct_Body( i_min , i_ulim , self.lazy_action[d] )
			self.b[d] ^= self.lazy_action[d]
			self.lazy_action[d] = L.point.copy()
		if self.lazy_multiplication[d] != M.one:
			self.IntervalMultiply_Body( i_min , i_ulim , self.lazy_multiplication[d] )
			# N加群性を使った。
			self.b[d] = self.b[d] * ( self.lazy_multiplication[d] ** self.N_sqrt )
			self.lazy_multiplication[d] = M.one.copy()

	def IntervalAct_Body(self,i_min,i_ulim,r):
		for i in R(i_min,i_ulim):self.a[i] ^= r

	def IntervalMultiply_Body(self,i_min,i_ulim,u):
		for i in R(i_min,i_ulim):self.a[i] *= u

	def IntervalProduct_Body(self,i_min,i_ulim):
		answer = M.one.copy()
		for i in R(i_min,i_ulim):answer *= self.a[i]
		return answer

I,R=input,range
J=lambda:map(int,I().split())
N=int(I())
A=list(J())
Q=int(I())
pe=[]
C=[0]*99
for i in R(2,99):
	if C[i]<1:
		pe+=[i]
		j=i*2
		while j<99:C[j],j=1,j+i
C=len(pe)
t=[]
for p in pe:
	E=[M.one.copy()for i in R(N)]
	for i in R(N):
		while A[i]%p<1:
			A[i]//=p
			E[i].val+=1
	t+=[IntervalMultiplyLazySqrtDecomposition(E)]
for q in R(Q):
	type,l,r,x=J()
	l-=1
	r-=1
	if type<2:
		for c in R(C):
			e=M.one.copy()
			while x%pe[c]<1:
				x//=pe[c]
				e.val+=1
			t[c].IntervalSet(l,r,e)
	elif type<3:
		for c in R(C):
			e=M.one.copy()
			while x%pe[c]<1:
				x//=pe[c]
				e.val+=1
			t[c].IntervalMultiply(l,r,e)
	else:
		answer=1
		for c in R(C):
			if pe[c]<=x:answer*=t[c].IntervalProduct(l,r).val+1
			else:break
		print(answer%998244353)
0