結果
| 問題 |
No.2626 Similar But Different Name
|
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2024-02-09 22:38:08 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 962 ms / 3,000 ms |
| コード長 | 10,780 bytes |
| コンパイル時間 | 2,824 ms |
| コンパイル使用メモリ | 216,192 KB |
| 最終ジャッジ日時 | 2025-02-19 03:55:35 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
//入力が必ずmod未満の時に使う.
struct mint{
long long v = 0;
mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;}
long long val(){return v;}
void modu(){v %= mod;}
mint repeat2mint(long long a,long long b){
mint ret = 1,p = a; int Log = 60;
if(b <= 2e9) Log = 30;
for(int i=0; i<Log; i++){if(b&(1LL<<i)) ret *= p; p *= p;}
return ret;
};
mint operator+(mint b){return (v+b.v)%mod;}
mint operator-(mint b){return (v-b.v+mod)%mod;}
mint operator*(mint b){return v*b.v%mod;}
mint operator/(mint b){
if(b.v == 0) assert(false);
return v*(repeat2mint(b.v,mod-2)).v%mod;
}
void operator+=(mint b){v = (v+b.v)%mod;}
void operator-=(mint b){v = (v-b.v+mod)%mod;}
void operator*=(mint b){v = v*b.v%mod;}
void operator/=(mint b){
if(b.v == 0) assert(false);
v = v*repeat2mint(b.v,mod-2).v%mod;
}
void operator++(int){v = (v+1)%mod; return;}
void operator--(int){v = (v-1+mod)%mod; return;}
bool operator==(mint b){if(v == b.v) return true; else return false;}
bool operator!=(mint b){if(v != b.v) return true; else return false;}
bool operator>(mint b){if(v > b.v) return true; else return false;}
bool operator>=(mint b){if(v >= b.v) return true; else return false;}
bool operator<(mint b){if(v < b.v) return true; else return false;}
bool operator<=(mint b){if(v <= b.v) return true; else return false;}
mint pow(long long x){return repeat2mint(v,x);}
mint inv(){return mint(1)/v;}
};
namespace to_fold{ //纏めて折り畳むためのやつ 苦労したが結局ほぼACLの写経.
int countzero(unsigned long long x){
if(x == 0) return 64;
else return __popcount((x&-x)-1);
}
pair<long long,long long> invgcd(long long a,long long b){
a = (a+b)%b;
if(a == 0) return {b,0};
long long x = 0,y = 1,memo = b;
while(a){
x -= y*(b/a); b %= a;
swap(a,b); swap(x,y);
}
x = (x+memo/b)%(memo/b);
return {b,x};
}
struct fftinfo{
vector<mint> root,iroot,rate2,irate2,rate3,irate3;
fftinfo(mint g){
int rank2 = countzero(mod-1);
root.resize(rank2+1),iroot = root;
rate2.resize(max(0,rank2-2+1)); irate2 = rate2;
rate3.resize(max(0,rank2-3+1)); irate3 = rate3;
root.at(rank2) = g.pow((mod-1)>>rank2);
iroot.at(rank2) = root.at(rank2).inv();
for(int i=rank2-1; i>=0; i--){
root.at(i) = root.at(i+1)*root.at(i+1);
iroot.at(i) = iroot.at(i+1)*iroot.at(i+1);
}
mint mul = 1,imul = 1;
for(int i=0; i<=rank2-2; i++){
rate2.at(i) = root.at(i+2)*mul;
irate2.at(i) = iroot.at(i+2)*imul;
mul *= iroot.at(i+2),imul *= root.at(i+2);
}
mul = 1,imul = 1;
for(int i=0; i<=rank2-3; i++){
rate3.at(i) = root.at(i+3)*mul;
irate3.at(i) = iroot.at(i+3)*imul;
mul *= iroot.at(i+3),imul *= root.at(i+3);
}
}
};
mint findroot(){
if(mod == 998244353) return mint(3);
else if(mod == 754974721) return mint(11);
else if(mod == 167772161) return mint(3);
else if(mod == 469762049) return mint(3);
long long p = mod-1;
vector<long long> P;
for(long long i=2; i*i<=p; i++){
if(p%i) continue;
while(p%i == 0) p /= i;
P.push_back(i);
}
if(p != 1) P.push_back(p);
p = mod-1;
random_device rnd; mt19937 mt(rnd());
while(true){
mint ret = mt()%mod;
if(ret == 1 || ret == 0) continue;
if(ret.pow(p) != 1) continue;
bool ok = true;
for(auto check : P) if(ret.pow(p/check) == 1){ok = false; break;}
if(ok) return ret;
} //O(√P)らしいです.
}
void NTT(vector<mint> &A,fftinfo &info){
int N = A.size(),ln = countzero(N);
int dep = 0;
while(dep < ln){
if(ln-dep == 1){
int p = 1<<(ln-dep-1);
mint rot = 1;
for(int o=0; o<(1<<dep); o++){
int offset = o<<(ln-dep);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
A.at(i+offset) = l+r; A.at(i+offset+p) = l-r;
}
if(o+1 != (1<<dep)) rot *= info.rate2.at(countzero(~(unsigned int)o));
}
dep++;
}
else{
int p = 1<<(ln-dep-2);
mint rot = 1,imag = info.root.at(2);
for(int o=0; o<(1<<dep); o++){
mint rot2 = rot*rot,rot3 = rot2*rot;
int offset = o<<(ln-dep);
for(int i=0; i<p; i++){
auto mod2 = 1ULL*mod*mod;
auto a0 = 1ULL*A.at(i+offset).v;
auto a1 = 1ULL*A.at(i+offset+p).v*rot.v;
auto a2 = 1ULL*A.at(i+offset+p+p).v*rot2.v;
auto a3 = 1ULL*A.at(i+offset+p+p+p).v*rot3.v;
auto a1m2a3im = 1ULL*(a1+mod2-a3+mod)%mod*imag.v;
auto m2a2 = mod2-a2;
A.at(i+offset) = (long long)((a0+a2+a1+a3)%mod);
A.at(i+offset+p) = (long long)((a0+a2+(2*mod2-(a1+a3)))%mod);
A.at(i+offset+p+p) = (long long)((a0+m2a2+a1m2a3im)%mod);
A.at(i+offset+p+p+p) = (long long)((a0+m2a2+(mod2-a1m2a3im))%mod);
}
if(o+1 != (1<<dep)) rot *= info.rate3.at(countzero(~(unsigned int)o));
}
dep += 2;
}
}
}
void INTT(vector<mint> &A,fftinfo &info){
int N = A.size(),ln = countzero(N);
int dep = ln;
while(dep){
if(dep == 1){
int p = 1<<(ln-dep);
mint irot = 1;
for(int o=0; o<(1<<(dep-1)); o++){
int offset = o<<(ln-dep+1);
for(int i=0; i<p; i++){
mint l = A.at(i+offset),r = A.at(i+offset+p);
A.at(i+offset) = l+r;
A.at(i+offset+p) = (long long)((unsigned long long)((mod+l.v-r.v)*irot.v)%mod);
}
if(o+1 != (1<<(dep-1))) irot *= info.irate2.at(countzero(~(unsigned int)o));
}
dep--;
}
else{
int p = 1<<(ln-dep);
mint irot = 1,iimag = info.iroot.at(2);
for(int o=0; o<(1<<(dep-2)); o++){
mint irot2 = irot*irot,irot3 = irot2*irot;
int offset = o<<(ln-dep+2);
for(int i=0; i<p; i++){
auto a0 = 1ULL*A.at(i+offset).v,a1 = 1ULL*A.at(i+offset+p).v;
auto a2 = 1ULL*A.at(i+offset+p+p).v,a3 = 1ULL*A.at(i+offset+p+p+p).v;
auto gotyagotya = 1ULL*((mod+a2-a3)*iimag.v%mod);
A.at(i+offset) = (long long)((a0+a1+a2+a3)%mod);
A.at(i+offset+p) = (long long)((a0+(mod-a1)+gotyagotya)*irot.v%mod);
A.at(i+offset+p+p) = (long long)((a0+a1+(mod-a2)+(mod-a3))*irot2.v%mod);
A.at(i+offset+p+p+p) = (long long)((a0+(mod-a1)+(mod-gotyagotya))*irot3.v%mod);
}
if(o+1 != (1<<(dep-2))) irot *= info.irate3.at(countzero(~(unsigned int)o));
}
dep -= 2;
}
}
}
vector<mint> convolution(vector<mint> &A,vector<mint> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
if(siza == 0 || sizb == 0) return {};
while(N <= sizc) N *= 2;
vector<mint> ca = A,cb = B;
ca.resize(N),cb.resize(N);
assert((mod-1)%N == 0);
mint root = findroot();
fftinfo info(root);
NTT(ca,info); NTT(cb,info);
for(int i=0; i<N; i++) ca.at(i) *= cb.at(i);
INTT(ca,info); ca.resize(sizc);
mint divN = mint(N).inv();
for(int i=0; i<sizc; i++) ca.at(i) *= divN;
return ca;
}
vector<long long> convolution_ll(vector<long long> &A,vector<long long> &B){
int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
if(siza == 0 || sizb == 0) return {};
unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;
unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;
assert(sizc <= (1<<24));
mod = mod1;
vector<mint> a(siza),b(sizb);
for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;
vector<mint> C1 = convolution(a,b);
mod = mod2;
for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;
vector<mint> C2 = convolution(a,b);
mod = mod3;
for(int i=0; i<siza; i++) a.at(i) = A.at(i)%mod;
for(int i=0; i<sizb; i++) b.at(i) = B.at(i)%mod;
vector<mint> C3 = convolution(a,b);
vector<long long> ret(sizc);
vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};
for(int i=0; i<sizc; i++){
unsigned long long x = 0;
x += (C1.at(i).v*i1)%mod1*m2m3;
x += (C2.at(i).v*i2)%mod2*m3m1;
x += (C3.at(i).v*i3)%mod3*m1m2;
long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;
if(diff < 0) diff += mod1;
x -= offset.at(diff%5);
ret.at(i) = x;
}
return ret;
}
}
using namespace to_fold;
vector<int> Zalgo(string s){
int l1 = 0,N = s.size();
vector<int> ret(N);
for(int i=1; i<N; i++){
int l2 = i-l1;
if(i+ret.at(l2) < l1+ret.at(l1)) ret.at(i) = ret.at(l2);
else{
int len = max(0,l1+ret.at(l1)-i);
while(i+len < N && s.at(len) == s.at(i+len)) len++;
ret.at(i) = len; l1 = i;
}
}
ret.at(0) = N;
return ret;
}
int main() {
int N,M,K; cin >> N >> M >> K;
string s,t; cin >> s >> t;
string st = "";
for(auto c : t){
if(isupper(c)) c -= 'A'-'a';
st += c;
}
st += "&";
for(auto c : s){
if(isupper(c)) c -= 'A'-'a';
st += c;
}
vector<int> Z = Zalgo(st);
reverse(t.begin(),t.end());
vector<mint> A1(N),B1(M),A2(N),B2(M);
for(int i=0; i<N; i++){if('a' <= s.at(i) && s.at(i) <= 'z') A1.at(i) = 1; else A2.at(i) = 1;}
for(int i=0; i<M; i++){if('a' <= t.at(i) && t.at(i) <= 'z') B2.at(i) = 1; else B1.at(i) = 1;}
vector<mint> C1= convolution(A1,B1);
vector<mint> C2 = convolution(A2,B2);
int answer = 0;
for(int i=M-1; i<N; i++){
if(Z.at(i+2) != M) continue;
mint now = C1.at(i)+C2.at(i);
if(1 <= now.v && now.v <= K) answer++;
}
cout << answer << endl;
}