結果
問題 | No.2524 Stripes |
ユーザー |
![]() |
提出日時 | 2023-11-16 04:24:22 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,265 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 283,660 KB |
最終ジャッジ日時 | 2024-09-26 04:57:19 |
合計ジャッジ時間 | 63,720 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 15 WA * 2 RE * 7 TLE * 1 |
ソースコード
import sysinput = sys.stdin.readlinefrom copy import deepcopy# 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*m#print(A,B)C=[[None for i in range(m)] for j in range(k)]for i in range(k):for j in range(m):ANS=[0]for pl in range(l):#print((A[i][pl][:],B[pl][j][:]),convolution(A[i][pl][:],B[pl][j][:]))ANS=plus(ANS,convolution(A[i][pl][:],B[pl][j][:]))#print(ANS)C[i][j]=ANS#print(C)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()A=[[[1],[0]],[[0,1],[1]]]B=[[[1],[0,1]],[[0],[1]]]X=[]for s in S:if s=="R":X.append(deepcopy(A))else:X.append(deepcopy(B))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=Y#print("!",X)Y=[[[1]],[[1]]]ANS=prod(X[0],Y,2,2,1)#print(ANS)for i in range(1,N+1):if i<len(ANS[0][0]):print((ANS[0][0][i]+ANS[1][0][i])%mod)else:print(0)