結果
問題 |
No.3227 Matrix Query
|
ユーザー |
![]() |
提出日時 | 2025-08-11 21:30:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,009 ms / 8,000 ms |
コード長 | 1,729 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 82,220 KB |
実行使用メモリ | 138,976 KB |
最終ジャッジ日時 | 2025-08-11 21:31:23 |
合計ジャッジ時間 | 53,078 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
class segtree: def __init__(self,n,mod): self.size=1 self.mod=mod while self.size<n: self.size*=2 self.dat=[[1,0,0,1] for i in range(self.size*2)] def update(self,x,a,b,c,d): x+=self.size self.dat[x][:]=[a,b,c,d] while x>1: x//=2 self.dat[x]=[0,0,0,0] for i in range(2): for j in range(2): for k in range(2): self.dat[x][i*2+j]+=self.dat[2*x][2*i+k]*self.dat[2*x+1][2*k+j] self.dat[x][i*2+j]%=self.mod def querry(self,a,b): a+=self.size b+=self.size v=[[1,0,0,1] for i in range(20)] ans=[1,0,0,1] count=0 while a<b: count+=1 if a&1: ans2=[0,0,0,0] for i in range(2): for j in range(2): for k in range(2): ans2[2*i+j]+=ans[2*i+k]*self.dat[a][2*k+j] ans2[2*i+j]%=self.mod ans=ans2[:] a+=1 if b&1: b-=1 v[count]=self.dat[b][:] a//=2 b//=2 for k in range(19,-1,-1): ans2=[0,0,0,0] for i in range(2): for j in range(2): for w in range(2): ans2[2*i+j]+=ans[2*i+w]*v[k][2*w+j] ans2[2*i+j]%=self.mod ans=ans2[:] return ans[:] mod,N=map(int,input().split()) Z=segtree(N,mod) A=[[[0]*2 for i in range(2)] for k in range(N)] for k in range(N): a,b=map(int,input().split()) c,d=map(int,input().split()) A[k][0]=[a,b] A[k][1]=[c,d] Z.update(k,a,b,c,d) Q=int(input()) for _ in range(Q): pos,l,r=map(int,input().split()) l-=1 r-=1 pos-=1 a,b=map(int,input().split()) c,d=map(int,input().split()) Z.update(pos,a,b,c,d) result=Z.querry(l,r+1) print(result[0],result[1]) print(result[2],result[3])