結果

問題 No.1548 [Cherry 2nd Tune B] 貴方と私とサイクルとモーメント
ユーザー sasa8uyauya
提出日時 2025-02-23 22:58:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,933 ms / 4,500 ms
コード長 3,562 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,888 KB
実行使用メモリ 117,692 KB
最終ジャッジ日時 2025-02-23 23:00:25
合計ジャッジ時間 79,617 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

M=998244353
B=448

class LST:
  def __init__(self):
    self.st1=[0]*B*B
    self.st2=[0]*B
    self.lt=[-1]*B
    return
  
  def apl(self,l,r,x):
    yl=l//B
    yr=r//B
    if self.lt[yl]!=-1:
      for i in range(B):
        self.st1[yl*B+i]=self.lt[yl]
      self.lt[yl]=-1
    if self.lt[yr]!=-1:
      for i in range(B):
        self.st1[yr*B+i]=self.lt[yr]
      self.lt[yr]=-1
    if yl==yr:
      for i in range(l,r+1):
        self.st1[i]=x
      self.st2[yl]=sum(self.st1[yl*B:yl*B+B])%M
    else:
      for i in range(l,yl*B+B):
        self.st1[i]=x
      self.st2[yl]=sum(self.st1[yl*B:yl*B+B])%M
      for i in range(yl+1,yr):
        self.st2[i]=x*B%M
        self.lt[i]=x
      for i in range(yr*B,r+1):
        self.st1[i]=x
      self.st2[yr]=sum(self.st1[yr*B:yr*B+B])%M
    return
  
  def prd(self,l,r):
    yl=l//B
    yr=r//B
    if self.lt[yl]!=-1:
      for i in range(B):
        self.st1[yl*B+i]=self.lt[yl]
      self.lt[yl]=-1
    if self.lt[yr]!=-1:
      for i in range(B):
        self.st1[yr*B+i]=self.lt[yr]
      self.lt[yr]=-1
    a=0
    if yl==yr:
      a+=sum(self.st1[l:r+1])%M
    else:
      a+=sum(self.st1[l:yl*B+B])%M
      a+=sum(self.st2[yl+1:yr])%M
      a+=sum(self.st1[yr*B:r+1])%M
    return a%M


q1=LST()
q2=LST()
q3=LST()
q4=LST()

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  v=a[i]
  q1.apl(i,i,v**1%M)
  q2.apl(i,i,v**2%M)
  q3.apl(i,i,v**3%M)
  q4.apl(i,i,v**4%M)

Q=int(input())
for _ in range(Q):
  que=list(map(int,input().split()))
  t=que[0]
  if t==0:
    _,l,r,m,v=que
    if l>r:
      l,r=r,l
    l-=1
    r-=1
    m-=1
    if l<m<r:
      q1.apl(l,r,v**1%M)
      q2.apl(l,r,v**2%M)
      q3.apl(l,r,v**3%M)
      q4.apl(l,r,v**4%M)
    else:
      q1.apl(0,l,v**1%M)
      q2.apl(0,l,v**2%M)
      q3.apl(0,l,v**3%M)
      q4.apl(0,l,v**4%M)
      q1.apl(r,n-1,v**1%M)
      q2.apl(r,n-1,v**2%M)
      q3.apl(r,n-1,v**3%M)
      q4.apl(r,n-1,v**4%M)
  if t==1:
    _,l,r,m=que
    if l>r:
      l,r=r,l
    l-=1
    r-=1
    m-=1
    s1=(q1.prd(l,r) if l<m<r else q1.prd(0,l)+q1.prd(r,n-1))%M
    L=r-l+1 if l<m<r else n-(r-l+1)+2
    m=s1*pow(L,M-2,M)
    g=0
    g+=s1
    g+=(-m)*L
    g*=pow(L,M-2,M)
    g%=M
    print(g)
  if t==2:
    _,l,r,m=que
    if l>r:
      l,r=r,l
    l-=1
    r-=1
    m-=1
    s1=(q1.prd(l,r) if l<m<r else q1.prd(0,l)+q1.prd(r,n-1))%M
    s2=(q2.prd(l,r) if l<m<r else q2.prd(0,l)+q2.prd(r,n-1))%M
    L=r-l+1 if l<m<r else n-(r-l+1)+2
    m=s1*pow(L,M-2,M)
    g=0
    g+=s2
    g+=2*(-m)*s1
    g+=((-m)**2)*L
    g*=pow(L,M-2,M)
    g%=M
    print(g)
  if t==3:
    _,l,r,m=que
    if l>r:
      l,r=r,l
    l-=1
    r-=1
    m-=1
    s1=(q1.prd(l,r) if l<m<r else q1.prd(0,l)+q1.prd(r,n-1))%M
    s2=(q2.prd(l,r) if l<m<r else q2.prd(0,l)+q2.prd(r,n-1))%M
    s3=(q3.prd(l,r) if l<m<r else q3.prd(0,l)+q3.prd(r,n-1))%M
    L=r-l+1 if l<m<r else n-(r-l+1)+2
    m=s1*pow(L,M-2,M)
    g=0
    g+=s3
    g+=3*(-m)*s2
    g+=3*((-m)**2)*s1
    g+=((-m)**3)*L
    g*=pow(L,M-2,M)
    g%=M
    print(g)
  if t==4:
    _,l,r,m=que
    if l>r:
      l,r=r,l
    l-=1
    r-=1
    m-=1
    s1=(q1.prd(l,r) if l<m<r else q1.prd(0,l)+q1.prd(r,n-1))%M
    s2=(q2.prd(l,r) if l<m<r else q2.prd(0,l)+q2.prd(r,n-1))%M
    s3=(q3.prd(l,r) if l<m<r else q3.prd(0,l)+q3.prd(r,n-1))%M
    s4=(q4.prd(l,r) if l<m<r else q4.prd(0,l)+q4.prd(r,n-1))%M
    L=r-l+1 if l<m<r else n-(r-l+1)+2
    m=s1*pow(L,M-2,M)
    g=0
    g+=s4
    g+=4*(-m)*s3
    g+=6*((-m)**2)*s2
    g+=4*((-m)**3)*s1
    g+=((-m)**4)*L
    g*=pow(L,M-2,M)
    g%=M
    print(g)
0