結果
問題 | No.2626 Similar But Different Name |
ユーザー | AngrySadEight |
提出日時 | 2024-02-09 17:52:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,873 ms / 3,000 ms |
コード長 | 7,906 bytes |
コンパイル時間 | 313 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 159,540 KB |
最終ジャッジ日時 | 2024-02-09 17:53:21 |
合計ジャッジ時間 | 39,207 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
55,592 KB |
testcase_01 | AC | 35 ms
55,592 KB |
testcase_02 | AC | 39 ms
55,592 KB |
testcase_03 | AC | 34 ms
55,592 KB |
testcase_04 | AC | 36 ms
55,592 KB |
testcase_05 | AC | 39 ms
61,956 KB |
testcase_06 | AC | 39 ms
61,956 KB |
testcase_07 | AC | 120 ms
77,716 KB |
testcase_08 | AC | 125 ms
77,528 KB |
testcase_09 | AC | 119 ms
77,608 KB |
testcase_10 | AC | 127 ms
77,872 KB |
testcase_11 | AC | 127 ms
78,088 KB |
testcase_12 | AC | 126 ms
77,868 KB |
testcase_13 | AC | 140 ms
78,076 KB |
testcase_14 | AC | 119 ms
77,840 KB |
testcase_15 | AC | 122 ms
77,988 KB |
testcase_16 | AC | 124 ms
77,928 KB |
testcase_17 | AC | 126 ms
77,928 KB |
testcase_18 | AC | 1,687 ms
155,820 KB |
testcase_19 | AC | 1,850 ms
155,756 KB |
testcase_20 | AC | 1,830 ms
155,748 KB |
testcase_21 | AC | 1,873 ms
156,500 KB |
testcase_22 | AC | 1,783 ms
155,772 KB |
testcase_23 | AC | 1,729 ms
155,192 KB |
testcase_24 | AC | 1,813 ms
155,496 KB |
testcase_25 | AC | 1,731 ms
155,672 KB |
testcase_26 | AC | 1,683 ms
155,188 KB |
testcase_27 | AC | 1,725 ms
155,796 KB |
testcase_28 | AC | 1,751 ms
155,136 KB |
testcase_29 | AC | 1,770 ms
159,540 KB |
testcase_30 | AC | 1,721 ms
155,108 KB |
testcase_31 | AC | 1,689 ms
155,752 KB |
testcase_32 | AC | 1,749 ms
155,196 KB |
testcase_33 | AC | 1,760 ms
155,208 KB |
testcase_34 | AC | 1,762 ms
155,260 KB |
testcase_35 | AC | 1,790 ms
155,168 KB |
testcase_36 | AC | 1,785 ms
155,260 KB |
testcase_37 | AC | 1,599 ms
155,816 KB |
ソースコード
# ACL-for-python: https://github.com/shakayami/ACL-for-python/blob/master/convolution.py class FFT(): def primitive_root_constexpr(self,m): if m==2:return 1 if m==167772161:return 3 if m==469762049:return 3 if m==754974721:return 11 if m==998244353:return 3 divs=[0]*20 divs[0]=2 cnt=1 x=(m-1)//2 while(x%2==0):x//=2 i=3 while(i*i<=x): if (x%i==0): divs[cnt]=i cnt+=1 while(x%i==0): x//=i i+=2 if x>1: divs[cnt]=x cnt+=1 g=2 while(1): ok=True for i in range(cnt): if pow(g,(m-1)//divs[i],m)==1: ok=False break if ok: return g g+=1 def bsf(self,x): res=0 while(x%2==0): res+=1 x//=2 return res rank2=0 root=[] iroot=[] rate2=[] irate2=[] rate3=[] irate3=[] def __init__(self,MOD): self.mod=MOD self.g=self.primitive_root_constexpr(self.mod) self.rank2=self.bsf(self.mod-1) self.root=[0 for i in range(self.rank2+1)] self.iroot=[0 for i in range(self.rank2+1)] self.rate2=[0 for i in range(self.rank2)] self.irate2=[0 for i in range(self.rank2)] self.rate3=[0 for i in range(self.rank2-1)] self.irate3=[0 for i in range(self.rank2-1)] self.root[self.rank2]=pow(self.g,(self.mod-1)>>self.rank2,self.mod) self.iroot[self.rank2]=pow(self.root[self.rank2],self.mod-2,self.mod) for i in range(self.rank2-1,-1,-1): self.root[i]=(self.root[i+1]**2)%self.mod self.iroot[i]=(self.iroot[i+1]**2)%self.mod prod=1;iprod=1 for i in range(self.rank2-1): self.rate2[i]=(self.root[i+2]*prod)%self.mod self.irate2[i]=(self.iroot[i+2]*iprod)%self.mod prod=(prod*self.iroot[i+2])%self.mod iprod=(iprod*self.root[i+2])%self.mod prod=1;iprod=1 for i in range(self.rank2-2): self.rate3[i]=(self.root[i+3]*prod)%self.mod self.irate3[i]=(self.iroot[i+3]*iprod)%self.mod prod=(prod*self.iroot[i+3])%self.mod iprod=(iprod*self.root[i+3])%self.mod def butterfly(self,a): n=len(a) h=(n-1).bit_length() LEN=0 while(LEN<h): if (h-LEN==1): p=1<<(h-LEN-1) rot=1 for s in range(1<<LEN): offset=s<<(h-LEN) for i in range(p): l=a[i+offset] r=a[i+offset+p]*rot a[i+offset]=(l+r)%self.mod a[i+offset+p]=(l-r)%self.mod rot*=self.rate2[(~s & -~s).bit_length()-1] rot%=self.mod LEN+=1 else: p=1<<(h-LEN-2) rot=1 imag=self.root[2] for s in range(1<<LEN): rot2=(rot*rot)%self.mod rot3=(rot2*rot)%self.mod offset=s<<(h-LEN) 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 a1na3imag=(a1-a3)%self.mod*imag a[i+offset]=(a0+a2+a1+a3)%self.mod a[i+offset+p]=(a0+a2-a1-a3)%self.mod a[i+offset+2*p]=(a0-a2+a1na3imag)%self.mod a[i+offset+3*p]=(a0-a2-a1na3imag)%self.mod rot*=self.rate3[(~s & -~s).bit_length()-1] rot%=self.mod LEN+=2 def butterfly_inv(self,a): n=len(a) h=(n-1).bit_length() LEN=h while(LEN): if (LEN==1): p=1<<(h-LEN) irot=1 for s in range(1<<(LEN-1)): offset=s<<(h-LEN+1) for i in range(p): l=a[i+offset] r=a[i+offset+p] a[i+offset]=(l+r)%self.mod a[i+offset+p]=(l-r)*irot%self.mod irot*=self.irate2[(~s & -~s).bit_length()-1] irot%=self.mod LEN-=1 else: p=1<<(h-LEN) irot=1 iimag=self.iroot[2] for s in range(1<<(LEN-2)): irot2=(irot*irot)%self.mod irot3=(irot*irot2)%self.mod offset=s<<(h-LEN+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] a2na3iimag=(a2-a3)*iimag%self.mod a[i+offset]=(a0+a1+a2+a3)%self.mod a[i+offset+p]=(a0-a1+a2na3iimag)*irot%self.mod a[i+offset+2*p]=(a0+a1-a2-a3)*irot2%self.mod a[i+offset+3*p]=(a0-a1-a2na3iimag)*irot3%self.mod irot*=self.irate3[(~s & -~s).bit_length()-1] irot%=self.mod LEN-=2 def convolution(self,a,b): n=len(a);m=len(b) if not(a) or not(b): return [] if min(n,m)<=40: res=[0]*(n+m-1) for i in range(n): for j in range(m): res[i+j]+=a[i]*b[j] res[i+j]%=self.mod return res z=1<<((n+m-2).bit_length()) a=a+[0]*(z-n) b=b+[0]*(z-m) self.butterfly(a) self.butterfly(b) c=[(a[i]*b[i])%self.mod for i in range(z)] self.butterfly_inv(c) iz=pow(z,self.mod-2,self.mod) for i in range(n+m-1): c[i]=(c[i]*iz)%self.mod return c[:n+m-1] def inv_gcd(a,b): a=a%b if a==0: return (b,0) s=b;t=a m0=0;m1=1 while(t): u=s//t s-=t*u m0-=m1*u s,t=t,s m0,m1=m1,m0 if m0<0: m0+=b//s return (s,m0) def crt(r,m): assert len(r)==len(m) n=len(r) r0=0;m0=1 for i in range(n): assert 1<=m[i] r1=r[i]%m[i] m1=m[i] if m0<m1: r0,r1=r1,r0 m0,m1=m1,m0 if (m0%m1==0): if (r0%m1!=r1): return (0,0) continue g,im=inv_gcd(m0,m1) u1=m1//g if ((r1-r0)%g): return (0,0) x=(r1-r0)//g % u1*im%u1 r0+=x*m0 m0*=u1 if r0<0: r0+=m0 return (r0,m0) mod1 = 998244353 mod2 = 754974721 CONV1 = FFT(mod1) CONV2 = FFT(mod2) def conv_ch(c): if 0 <= ord(c) - ord('A') <= 25: return (ord(c) - ord('A')) * 10000 + 1 else: return (ord(c) - ord('a')) * 10000 N, M, K = map(int, input().split()) S = str(input()) T = str(input()) sq_sum_s = [0 for _ in range(N + 1)] sq_sum_t = 0 val_s = [0 for _ in range(N)] val_t = [0 for _ in range(N)] for i in range(N): val = conv_ch(S[i]) sq_sum_s[i + 1] = sq_sum_s[i] + val * val val_s[i] = val for i in range(M): val = conv_ch(T[M - 1 - i]) sq_sum_t += val * val val_t[i] = val conv_st1 = CONV1.convolution(val_s, val_t) conv_st2 = CONV2.convolution(val_s, val_t) ans = 0 for i in range(M - 1, N): conv_val = crt((conv_st1[i], conv_st2[i]), (mod1, mod2)) diffs = sq_sum_s[i + 1] - sq_sum_s[i + 1 - M] + sq_sum_t - 2 * conv_val[0] if 1 <= diffs <= K: ans += 1 print(ans)