結果
| 問題 | No.2626 Similar But Different Name |
| ユーザー |
 hato336
|
| 提出日時 | 2024-02-09 22:53:34 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,596 bytes |
| コンパイル時間 | 4,714 ms |
| コンパイル使用メモリ | 314,192 KB |
| 実行使用メモリ | 13,632 KB |
| 最終ジャッジ日時 | 2024-09-28 16:04:56 |
| 合計ジャッジ時間 | 11,190 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 16 TLE * 1 -- * 18 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using namespace std;#define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__)#define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__)#define OVERLOAD_REP(_1, _2, _3, _4, name, ...) name#define REP1(n) for(ll i=0;i<n;i++)#define REP2(i, n) for (ll i=0;i<n;i++)#define REP3(i, a, n) for (ll i=a;i<n;i++)#define REP4(i, a, b, n) for(ll i=a;i<n;i+=b)#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)#define OVERLOAD_RREP(_1, _2, _3, _4, name, ...) name#define RREP1(n) for(ll i=n;i>=0;i--)#define RREP2(i, n) for(ll i=n;i>=0;i--)#define RREP3(i, a, n) for(ll i=n;i>=a;i--)#define RREP4(i, a, b, n) for(ll i=n;i>=a;i-=b)#define rrep(...) OVERLOAD_RREP(__VA_ARGS__, RREP4, RREP3, RREP2, RREP1)(__VA_ARGS__)#define foa(a,v) (auto& a : (v))#define uniq(a) sort(all(a));a.erase(unique(all(a)),end(a))#define len(n) (long long)(n).size()#define pb push_backusing ll = long long;using ld = long double;using ull = unsigned long long;using vi = vector<int>;using vvi = vector<vi>;using vvvi = vector<vvi>;using vll = vector<ll>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vs = vector<string>;using vvs = vector<vs>;using vvvs = vector<vvs>;using vld = vector<ld>;using vvld = vector<vld>;using vvvld = vector<vvld>;using vc = vector<char>;using vvc = vector<vc>;using vvvc = vector<vvc>;using pll = pair<ll,ll>;using vpll = vector<pll>;template<class... T>constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}template<class... T>constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}template<class... T>void input(T&... a){(cin >> ... >> a);}ll modpow(ll a,ll b,ll c){ll ans = 1;while (b){if (b & 1){ans *= a;ans %= c;}a *= a;a %= c;b /= 2;}return ans;}#define INT(...) int __VA_ARGS__; input(__VA_ARGS__)#define LL(...) ll __VA_ARGS__; input(__VA_ARGS__)#define ULL(...) ull __VA_ARGS__; input(__VA_ARGS__)#define LD(...) ld __VA_ARGS__; input(__VA_ARGS__)#define STR(...) string __VA_ARGS__; input(__VA_ARGS__)#define CHA(...) char __VA_ARGS__; input(__VA_ARGS__)#define VLL(name,length) vll name(length);rep(i,length){cin >> name[i];}#define VVLL(name,h,w) vvll name(h,vll(w));rep(i,h)rep(j,w){cin >> name[i][j];}#define VVVLL(name,a,b,c) vvvll name(a,vvll(b,vll(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];}#define VI(name,length) vi name(length);rep(i,length){cin >> name[i];}#define VVI(name,h,w) vvi name(h,vi(w));rep(i,h)rep(j,w){cin >> name[i][j];}#define VVVI(name,a,b,c) vvvi name(a,vvll(b,vi(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];}#define VLD(name,length) vld name(length);rep(i,length){cin >> name[i];}#define VVLD(name,h,w) vvld name(h,vld(w));rep(i,h)rep(j,w){cin >> name[i][j];}#define VVVLD(name,a,b,c) vvvld name(a,vvld(b,vld(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];}#define VC(name,length) vc name(length);rep(i,length){cin >> name[i];}#define VVC(name,h,w) vvc name(h,vc(w));rep(i,h)rep(j,w){cin >> name[i][j];}#define VVVC(name,a,b,c) vvvc name(a,vvc(b,vc(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];}#define VS(name,length) vs name(length);rep(i,length){cin >> name[i];}#define VVS(name,h,w) vvs name(h,vs(w));rep(i,h)rep(j,w){cin >> name[i][j];}#define VVVS(name,a,b,c) vvvs name(a,vvs(b,vs(c)));rep(i,a)rep(j,b)rep(k,c){cin >> name[i][j][k];}#define PLL(name) pll name;cin>>name.first>>name.second;#define VPLL(name,length) vpll name(length);rep(i,length){cin>>name[i].first>>name[i].second;}void print(){cout << "\n";}template<class T, class... Ts>void print(const T& a, const Ts&... b){cout << a;(cout << ... << (cout << ' ', b));cout << '\n';}void print(vll x){rep(i,len(x)){cout << x[i];if(i!=len(x)-1){cout << " ";}else{cout << '\n';}}}void print(vvll x){rep(i,len(x))rep(j,len(x[i])){cout << x[i][j];if(j!=len(x[i])-1){cout << " ";}else{cout << '\n';}}}using mint = modint;int main(){LL(n,m,k);STR(s);STR(t);ll mod = 998244353;mint::set_mod(998244353);vector<mint> h(n,0);rep(i,n-m+1){if(i == 0){rep(j,m){if('A' <= s[j] && s[j] <= 'Z'){h[0] += (s[j]-'A') * modpow(26,j,mod);}else{h[0] += (s[j]-'a') * modpow(26,j,mod);}}}else{h[i] = h[i-1] - (('A' <= s[i-1] && s[i-1] <= 'Z')?(s[i-1]-'A'):(s[i-1]-'a'));h[i] /= 26;h[i] += modpow(26,m-1,mod) * (('A' <= s[i+m-1] && s[i+m-1] <= 'Z')?(s[i+m-1]-'A'):(s[i+m-1]-'a'));}}mint tval = 0;rep(j,m){if('A' <= t[j] && t[j] <= 'Z'){tval += (t[j]-'A') * modpow(26,j,mod);}else{tval += (t[j]-'a') * modpow(26,j,mod);}}ll ans = 0;bitset<500010> sb;rep(i,m){if('A' <= s[i] && s[i] <= 'Z'){sb.set(i,1);}}bitset<500010> tb;rep(i,m){if('A' <= t[i] && t[i] <= 'Z'){tb.set(i,1);}}rep(i,n-m+1){if(h[i].val()==tval.val()){tb ^= (sb >> i);if(1 <= tb.count() && tb.count() <= k){ans++;}tb ^= (sb >> i);}if(i+m < n && 'A' <= s[i+m] && s[i+m] <= 'Z'){sb.set(i+m,1);}}print(ans);}