結果

問題 No.2626 Similar But Different Name
ユーザー maksimmaksim
提出日時 2024-02-09 22:03:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,456 bytes
コンパイル時間 2,259 ms
コンパイル使用メモリ 189,516 KB
実行使用メモリ 76,940 KB
最終ジャッジ日時 2024-09-28 15:17:56
合計ジャッジ時間 6,826 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
36,424 KB
testcase_01 AC 17 ms
36,936 KB
testcase_02 AC 15 ms
36,416 KB
testcase_03 AC 16 ms
36,420 KB
testcase_04 AC 16 ms
36,296 KB
testcase_05 AC 16 ms
37,184 KB
testcase_06 AC 16 ms
37,316 KB
testcase_07 AC 16 ms
36,676 KB
testcase_08 AC 17 ms
37,440 KB
testcase_09 AC 17 ms
37,704 KB
testcase_10 AC 17 ms
37,316 KB
testcase_11 AC 17 ms
37,704 KB
testcase_12 AC 16 ms
36,416 KB
testcase_13 AC 17 ms
37,320 KB
testcase_14 AC 17 ms
36,928 KB
testcase_15 AC 16 ms
36,804 KB
testcase_16 AC 17 ms
36,680 KB
testcase_17 AC 17 ms
36,420 KB
testcase_18 AC 175 ms
76,940 KB
testcase_19 AC 92 ms
56,560 KB
testcase_20 AC 88 ms
56,552 KB
testcase_21 AC 86 ms
56,384 KB
testcase_22 AC 174 ms
71,112 KB
testcase_23 AC 175 ms
70,628 KB
testcase_24 AC 167 ms
70,104 KB
testcase_25 AC 169 ms
70,436 KB
testcase_26 AC 172 ms
71,292 KB
testcase_27 AC 174 ms
72,096 KB
testcase_28 AC 173 ms
70,664 KB
testcase_29 AC 170 ms
68,928 KB
testcase_30 AC 171 ms
70,728 KB
testcase_31 WA -
testcase_32 AC 172 ms
70,744 KB
testcase_33 AC 173 ms
70,960 KB
testcase_34 AC 171 ms
69,060 KB
testcase_35 AC 173 ms
70,948 KB
testcase_36 AC 175 ms
69,016 KB
testcase_37 AC 173 ms
76,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define app push_back
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << '\n';}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
typedef long long ll;
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
template<int M, int K, int G> struct Fft {
  // 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...
  int g[1 << (K - 1)];
  Fft() : g() { //if tl constexpr...
    static_assert(K >= 2, "Fft: K >= 2 must hold");
    g[0] = 1;
    g[1 << (K - 2)] = G;
    for (int l = 1 << (K - 2); l >= 2; l >>= 1) {
      g[l >> 1] = (static_cast<long long>(g[l]) * g[l]) % M;
    }
    assert((static_cast<long long>(g[1]) * g[1]) % M == M - 1);
    for (int l = 2; l <= 1 << (K - 2); l <<= 1) {
      for (int i = 1; i < l; ++i) {
        g[l + i] = (static_cast<long long>(g[l]) * g[i]) % M;
      }
    }
  }
  void fft(vector<int> &x) const {
    const int n = x.size();
    assert(!(n & (n - 1)) && n <= 1 << K);
    for (int h = __builtin_ctz(n); h--; ) {
      const int l = 1 << h;
      for (int i = 0; i < n >> 1 >> h; ++i) {
        for (int j = i << 1 << h; j < ((i << 1) + 1) << h; ++j) {
          const int t = (static_cast<long long>(g[i]) * x[j | l]) % M;
          if ((x[j | l] = x[j] - t) < 0) x[j | l] += M;
          if ((x[j] += t) >= M) x[j] -= M;
        }
      }
    }
    for (int i = 0, j = 0; i < n; ++i) {
      if (i < j) std::swap(x[i], x[j]);
      for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {}
    }
  }
  vector<int> convolution(const vector<int> &a, const vector<int> &b) const {
    if(a.empty() || b.empty()) return {};
    const int na = a.size(), nb = b.size();
    int n, invN = 1;
    for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1;
    vector<int> x(n, 0), y(n, 0);
    std::copy(a.begin(), a.end(), x.begin());
    std::copy(b.begin(), b.end(), y.begin());
    fft(x);
    fft(y);
    for (int i = 0; i < n; ++i) x[i] = (((static_cast<long long>(x[i]) * y[i]) % M) * invN) % M;
    std::reverse(x.begin() + 1, x.end());
    fft(x);
    x.resize(na + nb - 1);
    return x;
  }
};
Fft<998244353,23,31> muls;
vector<int> form(vector<int> v,int n)
{
    while(v.size()<n) v.push_back(0);
    while(v.size()>n) v.pop_back();
    return v;
}
vector<int> operator *(vector<int> v1,vector<int> v2)
{
    return muls.convolution(v1,v2);
}
vector<int> operator +(vector<int> v1,vector<int> v2)
{
    while(v2.size()<v1.size()) v2.push_back(0); while(v1.size()<v2.size()) v1.push_back(0);
    for(int i=0;i<v1.size();++i) {v1[i]+=v2[i];if(v1[i]>=p) v1[i]-=p; else if(v1[i]<0) v1[i]+=p;}
    return v1;
}
vector<int> operator -(vector<int> v1,vector<int> v2)
{
    int sz=max(v1.size(),v2.size());while(v1.size()<sz) v1.push_back(0); while(v2.size()<sz) v2.push_back(0);
    for(int i=0;i<sz;++i) {v1[i]-=v2[i];if(v1[i]<0) v1[i]+=p; else if(v1[i]>=p) v1[i]-=p;} return v1;
}
vector<int> trmi(vector<int> v)
{
    for(int i=1;i<v.size();i+=2) {if(v[i]>0) v[i]=p-v[i]; else v[i]=(-v[i]);}
    return v;
}
vector<int> deriv(vector<int> v)
{
    if(v.empty()) return{};
    vector<int> ans(v.size()-1);
    for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;
    return ans;
}
vector<int> integ(vector<int> v)
{
    vector<int> ans(v.size()+1);ans[0]=0;
    for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;
    return ans;
}
vector<int> mul(vector<vector<int> > v)
{
    if(v.size()==1) return v[0];
    vector<vector<int> > v1,v2;for(int i=0;i<v.size()/2;++i) v1.push_back(v[i]); for(int i=v.size()/2;i<v.size();++i) v2.push_back(v[i]);
    return muls.convolution(mul(v1),mul(v2));
}
vector<int> inv1(vector<int> v,int n)
{
    assert(v[0]!=0);
    int sz=1;v=form(v,n);vector<int> a={inv(v[0])};
    while(sz<n)
    {
        vector<int> vsz;for(int i=0;i<min(n,2*sz);++i) vsz.push_back(v[i]);
        vector<int> b=((vector<int>) {1})-muls.convolution(a,vsz);
        for(int i=0;i<sz;++i) assert(b[i]==0);
        b.erase(b.begin(),b.begin()+sz);
        vector<int> c=muls.convolution(b,a);
        for(int i=0;i<sz;++i) a.push_back(c[i]);
        sz*=2;
    }
    return form(a,n);
}
vector<int> inv(vector<int> v,int n)
{
    v=form(v,n);assert(v[0]!=0);if(v.size()==1) {return {inv(v[0])};} vector<int> v1=trmi(v);
    vector<int> a=v1*v;a=form(a,2*n);
    vector<int> b((n+1)/2);for(int i=0;i<b.size();++i) b[i]=a[2*i];
    vector<int> ans1=inv(b,b.size());vector<int> ans2(n);for(int i=0;i<n;++i) {if(i%2==0) ans2[i]=ans1[i/2]; else ans2[i]=0;}
    return form(v1*ans2,n);
}
vector<int> operator/(vector<int> a,vector<int> b)
{
    while(!a.empty() && a.back()==0) a.pop_back(); while(!b.empty() && b.back()==0) b.pop_back();
    int n=a.size();int m=b.size();if(n<m) return {};
    reverse(a.begin(),a.end());reverse(b.begin(),b.end());vector<int> ans=a*inv(b,n-m+1);while(ans.size()>n-m+1) ans.pop_back();
    reverse(ans.begin(),ans.end());while(!ans.empty() && ans.back()==0) ans.pop_back();return ans;
}
vector<int> operator%(vector<int> a,vector <int> b)
{
    vector<int> ans=a-b*(a/b);while(!ans.empty() && ans.back()==0) ans.pop_back(); return ans;
}
int arr[256];
const int maxn=5e5+5;
int prs[maxn];int prt[maxn];bool ok[maxn];
mt19937 rnd;
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    for(char c='a';c<='z';++c) {arr[c]=rnd();arr[c]%=p;}
    for(char c='A';c<='Z';++c) {debug(c,((char) (c-'A'+'a')));arr[c]=(arr[c-'A'+'a']+1)%p;debug(arr[c],arr[c-'A'+'a']);}
    int n,m,k;cin>>n>>m>>k;
    string s,t;cin>>s>>t;
    for(int i=0;i<s.size();++i) {prs[i+1]=prs[i]+arr[s[i]]*arr[s[i]];prs[i+1]%=p;}
    for(int i=0;i<t.size();++i) {prt[i+1]=prt[i]+arr[t[i]]*arr[t[i]];prt[i+1]%=p;}
    vector<int> bs(s.size()),bt(t.size());
    for(int i=0;i<s.size();++i) {bs[i]=arr[s[i]];}
    for(int i=0;i<t.size();++i) {bt[i]=arr[t[i]];}
    reverse(all(bt));vector<int> b=bs*bt;
    debug(bs[0],bs[1],bt[0],bt[1]);
    int answ=0;
    for(int i=0;i<=s.size()-t.size();++i)
    {
        int res=prs[i+t.size()]-prs[i];res+=prt[t.size()];res%=p;
        res-=2*b[t.size()+i-1];res%=p;res+=p;res%=p;
        debug(i,res);
        if(res>=1 && res<=k)
        {
            ok[i]=1;
        }
    }
    cout<<accumulate(ok,ok+maxn,0LL);
    return 0;
}
0