結果
問題 | No.2265 Xor Range Substring Sum Query |
ユーザー |
![]() |
提出日時 | 2023-03-09 14:57:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,430 ms / 5,000 ms |
コード長 | 1,164 bytes |
コンパイル時間 | 165 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 102,848 KB |
最終ジャッジ日時 | 2024-09-25 00:31:43 |
合計ジャッジ時間 | 34,754 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
from sys import stdininput=lambda :stdin.readline()[:-1]mod=998244353n=int(input())N=1<<nS=input()m=n//2node=[[0]*N for i in range(m+1)]pow11=[1]*(N+1)pow2=[1]*(N+1)for i in range(1,N+1):pow11[i]=pow11[i-1]*11%modpow2[i]=pow2[i-1]*2%modfor i in range(N):node[0][i]=int(S[i])def calc(fL,Lsize,fR,Rsize):num=fL*pow11[Rsize]+fR*pow2[Lsize]return num%moddef merge(i,j):L=jR=L^(1<<(i-1))node[i][L]=calc(node[i-1][L],1<<(i-1),node[i-1][R],1<<(i-1))for i in range(m):for j in range(N):merge(i+1,j)q=int(input())for _ in range(q):query=list(map(int,input().split()))if query[0]==1:x,y=query[1:]node[0][x]=yfor i in range(m):s=1<<il=(x//(2*s))*2*sr=l+2*sfor j in range(l,r):merge(i+1,j)else:L,R,x=query[1:]R+=1res=0size=0s=(1<<m)while L<R and L%s!=0:res=calc(res,size,node[0][L^x],1)L+=1size+=1while L+s<=R:res=calc(res,size,node[m][L^x],s)L+=ssize+=swhile L<R:res=calc(res,size,node[0][L^x],1)L+=1size+=1print(res)