結果
問題 | No.2524 Stripes |
ユーザー |
![]() |
提出日時 | 2023-11-16 04:36:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 6,581 ms / 7,000 ms |
コード長 | 3,033 bytes |
コンパイル時間 | 476 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 266,708 KB |
最終ジャッジ日時 | 2024-09-26 05:00:20 |
合計ジャッジ時間 | 55,771 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
import sysinput = sys.stdin.readline# FFT# mod=998244353 における、NTTによる高速フーリエ変換、畳み込み# 他の提出を参考にしており、あまり理解できていません……mod=998244353Weight=[1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897,350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432, 0]Weight_inv=[1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727,358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224, 0]def fft(A,n,h,inverse=0):if inverse==0:for i in range(h):m=1<<(h-i-1)for j in range(1<<i):w=1ij=j*m*2wk=Weight[h-i]for k in range(m):A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m])%mod,(A[ij+k]-A[ij+k+m])*w%modw=w*wk%modelse:for i in range(h):m=1<<ifor j in range(1<<(h-i-1)):w=1ij=j*m*2wk=Weight_inv[i+1]for k in range(m):A[ij+k],A[ij+k+m]=(A[ij+k]+A[ij+k+m]*w)%mod,(A[ij+k]-A[ij+k+m]*w)%modw=w*wk%modif inverse==1:INV_n=pow(n,mod-2,mod)for i in range(n):A[i]=A[i]*INV_n%modreturn Adef convolution(A,B):FFTLEN=len(A)+len(B)-1h=FFTLEN.bit_length()LEN=2**hA+=[0]*(LEN-len(A)) # A,Bのサイズを2ベキに揃えるB+=[0]*(LEN-len(B))A_FFT=fft(A,LEN,h)B_FFT=fft(B,LEN,h)for i in range(len(A)):A[i]=A[i]*B[i]%modA=fft(A,LEN,h,1)return A[:FFTLEN]# 行列の計算(numpyを使えないとき,modを使用)def prod(A,B,k,l,m):# A:k*l,B:l*mC=[[[] for i in range(m)] for j in range(k)]for i in range(k):for j in range(m):C[i][j]=plus(convolution(A[i][0][:],B[0][j][:]),convolution(A[i][1][:],B[1][j][:]))return Cdef plus(A,B):C=[0]*max(len(A),len(B))for i in range(len(A)):C[i]+=A[i]for i in range(len(B)):C[i]+=B[i]return CN=int(input())S=input().strip()X=[]for s in S:if s=="R":X.append([[[1],[0]],[[0,1],[1]]])else:X.append([[[1],[0,1]],[[0],[1]]])while len(X)>=2:Y=[]for i in range(0,len(X),2):if i+1<len(X):Y.append(prod(X[i],X[i+1],2,2,2))else:Y.append(X[i])X=YY=[[[1]],[[1]]]ANS=prod(X[0],Y,2,2,1)for i in range(1,N+1):score=0if i<len(ANS[0][0]):score+=ANS[0][0][i]if i<len(ANS[1][0]):score+=ANS[1][0][i]print(score%mod)