結果
問題 | No.2626 Similar But Different Name |
ユーザー | zeta7532 |
提出日時 | 2024-01-11 01:41:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 336 ms / 3,000 ms |
コード長 | 2,707 bytes |
コンパイル時間 | 2,516 ms |
コンパイル使用メモリ | 215,600 KB |
実行使用メモリ | 75,836 KB |
最終ジャッジ日時 | 2024-01-11 01:41:39 |
合計ジャッジ時間 | 10,468 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
7,204 KB |
testcase_01 | AC | 6 ms
7,204 KB |
testcase_02 | AC | 6 ms
7,204 KB |
testcase_03 | AC | 5 ms
7,204 KB |
testcase_04 | AC | 6 ms
7,204 KB |
testcase_05 | AC | 5 ms
7,204 KB |
testcase_06 | AC | 6 ms
7,204 KB |
testcase_07 | AC | 6 ms
7,468 KB |
testcase_08 | AC | 6 ms
7,468 KB |
testcase_09 | AC | 7 ms
7,468 KB |
testcase_10 | AC | 8 ms
7,724 KB |
testcase_11 | AC | 8 ms
7,724 KB |
testcase_12 | AC | 7 ms
7,468 KB |
testcase_13 | AC | 8 ms
7,724 KB |
testcase_14 | AC | 7 ms
7,724 KB |
testcase_15 | AC | 8 ms
7,724 KB |
testcase_16 | AC | 8 ms
7,724 KB |
testcase_17 | AC | 8 ms
7,724 KB |
testcase_18 | AC | 315 ms
75,836 KB |
testcase_19 | AC | 164 ms
43,604 KB |
testcase_20 | AC | 162 ms
43,604 KB |
testcase_21 | AC | 163 ms
43,604 KB |
testcase_22 | AC | 336 ms
66,792 KB |
testcase_23 | AC | 307 ms
67,236 KB |
testcase_24 | AC | 303 ms
65,412 KB |
testcase_25 | AC | 306 ms
67,620 KB |
testcase_26 | AC | 330 ms
67,148 KB |
testcase_27 | AC | 304 ms
69,720 KB |
testcase_28 | AC | 306 ms
66,972 KB |
testcase_29 | AC | 308 ms
65,320 KB |
testcase_30 | AC | 322 ms
67,476 KB |
testcase_31 | AC | 301 ms
68,168 KB |
testcase_32 | AC | 305 ms
67,500 KB |
testcase_33 | AC | 308 ms
69,720 KB |
testcase_34 | AC | 321 ms
65,396 KB |
testcase_35 | AC | 296 ms
66,212 KB |
testcase_36 | AC | 302 ms
65,396 KB |
testcase_37 | AC | 313 ms
75,836 KB |
ソースコード
#include <bits/stdc++.h> #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; using ll = long long; const ll mod = 998244353; #define fi first #define se second #define rep(i,n) for(ll i=0;i<n;i++) #define all(x) x.begin(),x.end() #define faster ios::sync_with_stdio(false);cin.tie(nullptr) const ll root = 3; ll modpow(ll A,ll N){ ll res=1; while(N){ if(N&1) res=res*A%mod; A=A*A%mod; N>>=1; } return res; } ll modinv(ll A){return modpow(A,mod-2);} void NTT(vector<ll> &A,const bool rev=false){ vector<ll> B(A.size(),0); ll R=mod-1-(mod-1)/((ll)A.size()); if(rev) R=(mod-1)/((ll)A.size()); ll s=modpow(root,R); vector<ll> power((ll)A.size()/2+1,1); rep(i,(ll)A.size()/2) power[i+1]=(power[i]*s)%mod; ll cur=(ll)A.size()/2; for(ll i=1;i<(ll)A.size();i*=2){ rep(j,cur){ rep(k,i){ ll p=A[k+i*j]; ll q=A[k+i*j+(ll)A.size()/2]; B[k+2*i*j]=(p+q)%mod; B[k+2*i*j+i]=(p+mod-q)*power[i*j]%mod; } } swap(A,B); cur/=2; } if(rev){ s=modinv((ll)A.size()); rep(i,(ll)A.size()) A[i]=(A[i]*s)%mod; } } vector<ll> convolution(vector<ll> A,vector<ll> B){ ll size_=1; while(size_<=(ll)A.size()+(ll)B.size()-1) size_*=2; while(A.size()<size_) A.push_back(0); while(B.size()<size_) B.push_back(0); NTT(A); NTT(B); rep(i,size_) A[i]=(A[i]*B[i])%mod; NTT(A,true); return A; } int main() { ll N,M,K; cin >> N >> M >> K; string s,t; cin >> s >> t; vector<ll> po(500500,1); rep(i,500500-1) po[i+1]=po[i]*100%mod; vector<ll> S(N),T(M); vector<ll> A0(N),A1(N); vector<ll> B0(M),B1(M); rep(i,N){ if('a'<=s[i]&&s[i]<='z') S[i]=(s[i]-'a')+1,A0[i]=0; if('A'<=s[i]&&s[i]<='Z') S[i]=(s[i]-'A')+1,A0[i]=1; S[i]=S[i]*po[i]%mod; A1[i]=1-A0[i]; } rep(i,M){ if('a'<=t[i]&&t[i]<='z') T[i]=(t[i]-'a')+1,B0[i]=0; if('A'<=t[i]&&t[i]<='Z') T[i]=(t[i]-'A')+1,B0[i]=1; T[i]=T[i]*po[i]%mod; B1[i]=1-B0[i]; } reverse(all(B0)); reverse(all(B1)); vector<ll> C0=convolution(A0,B1); vector<ll> C1=convolution(A1,B0); vector<ll> cumS(N+1,0),cumT(M+1,0); rep(i,N) cumS[i+1]=(cumS[i]+S[i])%mod; rep(i,M) cumT[i+1]=(cumT[i]+T[i])%mod; ll ans=0; rep(i,N-M+1){ bool ok=true; if((cumS[i+M]+mod-cumS[i])%mod!=cumT[M]*po[i]%mod) ok=false; if((C0[i+M-1]+C1[i+M-1])==0||K<(C0[i+M-1]+C1[i+M-1])) ok=false; if(ok) ans++; } cout << ans << endl; return 0; }