結果
問題 | No.1195 数え上げを愛したい(文字列編) |
ユーザー | 👑 Kazun |
提出日時 | 2022-03-19 04:24:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 885 ms / 3,000 ms |
コード長 | 8,158 bytes |
コンパイル時間 | 177 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 131,932 KB |
最終ジャッジ日時 | 2024-10-03 18:16:33 |
合計ジャッジ時間 | 15,433 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 885 ms
131,688 KB |
testcase_01 | AC | 881 ms
131,432 KB |
testcase_02 | AC | 884 ms
131,932 KB |
testcase_03 | AC | 314 ms
89,772 KB |
testcase_04 | AC | 347 ms
91,380 KB |
testcase_05 | AC | 328 ms
75,136 KB |
testcase_06 | AC | 45 ms
54,144 KB |
testcase_07 | AC | 45 ms
54,400 KB |
testcase_08 | AC | 253 ms
85,064 KB |
testcase_09 | AC | 877 ms
131,296 KB |
testcase_10 | AC | 497 ms
103,288 KB |
testcase_11 | AC | 849 ms
128,516 KB |
testcase_12 | AC | 835 ms
127,852 KB |
testcase_13 | AC | 699 ms
115,708 KB |
testcase_14 | AC | 461 ms
100,844 KB |
testcase_15 | AC | 497 ms
102,792 KB |
testcase_16 | AC | 479 ms
101,880 KB |
testcase_17 | AC | 259 ms
84,992 KB |
testcase_18 | AC | 832 ms
127,940 KB |
testcase_19 | AC | 832 ms
127,824 KB |
testcase_20 | AC | 709 ms
116,524 KB |
testcase_21 | AC | 844 ms
128,348 KB |
testcase_22 | AC | 554 ms
106,472 KB |
testcase_23 | AC | 46 ms
54,528 KB |
testcase_24 | AC | 45 ms
54,528 KB |
testcase_25 | AC | 45 ms
54,144 KB |
ソースコード
class Convoluter: def __init__(self): self.primitive=self.__primitive_root() self.__build_up() def __primitive_root(self): p=Mod if p==2: return 1 if p==998244353: return 3 if p==10**9+7: return 5 if p==163577857: return 23 if p==167772161: return 3 if p==469762049: return 3 fac=[] q=2 v=p-1 while v>=q*q: e=0 while v%q==0: e+=1 v//=q if e>0: fac.append(q) q+=1 if v>1: fac.append(v) g=2 while g<p: if pow(g,p-1,p)!=1: return None flag=True for q in fac: if pow(g,(p-1)//q,p)==1: flag=False break if flag: return g g+=1 #参考元: https://judge.yosupo.jp/submission/72676 def __build_up(self): rank2=(~(Mod-1)&(Mod-2)).bit_length() root=[0]*(rank2+1); iroot=[0]*(rank2+1) rate2=[0]*max(0, rank2-1); irate2=[0]*max(0, rank2-1) rate3=[0]*max(0, rank2-2); irate3=[0]*max(0, rank2-2) root[-1]=pow(self.primitive, (Mod-1)>>rank2, Mod) iroot[-1]=pow(root[-1], Mod-2, Mod) for i in range(rank2)[::-1]: root[i]=root[i+1]*root[i+1]%Mod iroot[i]=iroot[i+1]*iroot[i+1]%Mod prod=iprod=1 for i in range(rank2-1): rate2[i]=root[i+2]*prod%Mod irate2[i]=iroot[i+2]*prod%Mod prod*=iroot[i+2]; prod%=Mod iprod*=root[i+2]; iprod%=Mod prod=iprod = 1 for i in range(rank2-2): rate3[i]=root[i + 3]*prod%Mod irate3[i]=iroot[i + 3]*iprod%Mod prod*=iroot[i + 3]; prod%=Mod iprod*=root[i + 3]; iprod%=Mod self.root=root; self.iroot=iroot self.rate2=rate2; self.irate2=irate2 self.rate3=rate3; self.irate3=irate3 #参考元 https://judge.yosupo.jp/submission/72676 def NTT(self,A): """A に Mod を法とする数論変換を施す ※ Mod はグローバル変数から指定 References: https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp https://judge.yosupo.jp/submission/72676 """ N=len(A) H=(N-1).bit_length() l=0 I=self.root[2] rate2=self.rate2; rate3=self.rate3 while l<H: if H-l==1: p=1<<(H-l-1) rot=1 for s in range(1<<l): offset=s<<(H-l) for i in range(p): x=A[i+offset]; y=A[i+offset+p]*rot%Mod A[i+offset]=(x+y)%Mod A[i+offset+p]=(x-y)%Mod if s+1!=1<<l: rot*=rate2[(~s&-~s).bit_length()-1] rot%=Mod l+=1 else: p=1<<(H-l-2) rot=1 for s in range(1<<l): rot2=rot*rot%Mod rot3=rot2*rot%Mod offset=s<<(H-l) for i in range(p): a0=A[i+offset] a1=A[i+offset+p]*rot a2=A[i+offset+2*p]*rot2 a3=A[i+offset+3*p]*rot3 alpha=(a1-a3)%Mod*I A[i+offset]=(a0+a2+a1+a3)%Mod A[i+offset+p]=(a0+a2-a1-a3)%Mod A[i+offset+2*p]=(a0-a2+alpha)%Mod A[i+offset+3*p]=(a0-a2-alpha)%Mod if s+1!=1<<l: rot*=rate3[(~s&-~s).bit_length()-1] rot%=Mod l+=2 #参考元 https://judge.yosupo.jp/submission/72676 def Inverse_NTT(self, A): """A を Mod を法とする逆数論変換を施す ※ Mod はグローバル変数から指定 References: https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp https://judge.yosupo.jp/submission/72676 """ N=len(A) H=(N-1).bit_length() l=H J=self.iroot[2] irate2=self.rate2; irate3=self.irate3 while l: if l==1: p=1<<(H-l) irot=1 for s in range(1<<(l-1)): offset=s<<(H-l+1) for i in range(p): x=A[i+offset]; y=A[i+offset+p] A[i+offset]=(x+y)%Mod A[i+offset+p]=(x-y)*irot%Mod if s+1!=1<<(l-1): irot*=irate2[(~s&-~s).bit_length()-1] irot%=Mod l-=1 else: p=1<<(H-l) irot=1 for s in range(1<<(l-2)): irot2=irot*irot%Mod irot3=irot2*irot%Mod offset=s<<(H-l+2) for i in range(p): a0=A[i+offset] a1=A[i+offset+p] a2=A[i+offset+2*p] a3=A[i+offset+3*p] beta=(a2-a3)*J%Mod A[i+offset]=(a0+a1+a2+a3)%Mod A[i+offset+p]=(a0-a1+beta)*irot%Mod A[i+offset+2*p]=(a0+a1-a2-a3)*irot2%Mod A[i+offset+3*p]=(a0-a1-beta)*irot3%Mod if s+1!=1<<(l-2): irot*=irate3[(~s&-~s).bit_length()-1] irot%=Mod l-=2 N_inv=pow(N,Mod-2,Mod) for i in range(N): A[i]=N_inv*A[i]%Mod def Convolution(self, A, B): """ A, B で Mod を法とする畳み込みを求める. ※ Mod はグローバル変数から指定 """ if not A or not B: return [] N=len(A) M=len(B) L=N+M-1 if min(N,M)<=20: if N<M: N,M=M,N A,B=B,A C=[0]*L for i in range(N): for j in range(M): C[i+j]+=A[i]*B[j] C[i+j]%=Mod return C H=L.bit_length() K=1<<H A=A+[0]*(K-N) B=B+[0]*(K-M) self.NTT(A) self.NTT(B) for i in range(K): A[i]=A[i]*B[i]%Mod self.Inverse_NTT(A) return A[:L] def Autocorrelation(self, A): """ A 自身に対して,Mod を法とする畳み込みを求める. ※ Mod はグローバル変数から指定 """ N=len(A) L=2*N-1 if N<=20: C=[0]*L for i in range(N): for j in range(N): C[i+j]+=A[i]*A[j] C[i+j]%=Mod return C H=L.bit_length() K=1<<H A=A+[0]*(K-N) self.NTT(A) for i in range(K): A[i]=A[i]*A[i]%Mod self.Inverse_NTT(A) return A[:L] def Multiple_Convolution(self, *A): """ A=(A[0], A[1], ..., A[d-1]) で Mod を法とする畳み込みを行う. """ from heapq import heapify,heappush,heappop Q=[(len(a), a) for a in A] heapify(Q) while len(Q)>1: m,a=heappop(Q) n,b=heappop(Q) heappush(Q, (m+n-1, self.Convolution(a,b))) return Q[0][1] #================================================== S=input() N=len(S) chi=[0]*26 for a in S: chi[ord(a)-ord("a")]+=1 Mod=998244353; Conv=Convoluter() Fact=[1]*(N+1) Fact_inv=[1]*(N+1) for i in range(1,N+1): Fact[i]=i*Fact[i-1]%Mod Fact_inv[i]=pow(Fact[i],Mod-2,Mod) A=Conv.Multiple_Convolution(*[Fact_inv[:chi[c]+1] for c in range(26)]) X=0 for d,a in enumerate(A): if d>=1: X+=Fact[d]*a X%=Mod print(X)