結果

問題 No.2626 Similar But Different Name
ユーザー GOTKAKOGOTKAKO
提出日時 2024-02-09 22:38:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 828 ms / 3,000 ms
コード長 10,780 bytes
コンパイル時間 2,789 ms
コンパイル使用メモリ 225,900 KB
実行使用メモリ 57,172 KB
最終ジャッジ日時 2024-09-28 15:50:35
合計ジャッジ時間 18,890 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 4 ms
6,820 KB
testcase_08 AC 3 ms
6,816 KB
testcase_09 AC 3 ms
6,820 KB
testcase_10 AC 7 ms
6,816 KB
testcase_11 AC 6 ms
6,820 KB
testcase_12 AC 4 ms
6,816 KB
testcase_13 AC 6 ms
6,816 KB
testcase_14 AC 6 ms
6,820 KB
testcase_15 AC 6 ms
6,816 KB
testcase_16 AC 7 ms
6,816 KB
testcase_17 AC 6 ms
6,816 KB
testcase_18 AC 808 ms
57,168 KB
testcase_19 AC 428 ms
28,844 KB
testcase_20 AC 424 ms
28,104 KB
testcase_21 AC 422 ms
28,248 KB
testcase_22 AC 802 ms
49,536 KB
testcase_23 AC 801 ms
49,676 KB
testcase_24 AC 800 ms
47,832 KB
testcase_25 AC 811 ms
48,564 KB
testcase_26 AC 815 ms
49,652 KB
testcase_27 AC 818 ms
49,960 KB
testcase_28 AC 801 ms
49,036 KB
testcase_29 AC 812 ms
47,696 KB
testcase_30 AC 806 ms
48,416 KB
testcase_31 AC 803 ms
49,304 KB
testcase_32 AC 800 ms
49,764 KB
testcase_33 AC 825 ms
49,836 KB
testcase_34 AC 800 ms
47,844 KB
testcase_35 AC 796 ms
49,336 KB
testcase_36 AC 804 ms
47,852 KB
testcase_37 AC 828 ms
57,172 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0