結果
| 問題 | No.2761 Substitute and Search |
| ユーザー |
 Yoshiki Yokota
|
| 提出日時 | 2025-04-29 22:31:47 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,826 ms / 4,000 ms |
| コード長 | 39,739 bytes |
| コンパイル時間 | 21,071 ms |
| コンパイル使用メモリ | 638,824 KB |
| 実行使用メモリ | 138,368 KB |
| 最終ジャッジ日時 | 2025-04-29 22:32:25 |
| 合計ジャッジ時間 | 34,091 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:750:17: warning: ‘hs.Hash61::hash_rev’ may be used uninitialized [-Wmaybe-uninitialized]
750 | if (bit[i].sum(t.size()).hash_rev == hs.hash_rev) ++ans;
| ^~
main.cpp:746:20: note: ‘hs.Hash61::hash_rev’ was declared here
746 | Hash61 hs(t);
| ^~
ソースコード
// #pragma GCC target("avx2")
#pragma GCC optimize("O2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
// #include <atcoder/all>
#if __has_include(<boost/algorithm/string.hpp>)
#include <boost/algorithm/string.hpp>
#endif
#if __has_include(<boost/algorithm/cxx11/all_of.hpp>)
#include <boost/algorithm/cxx11/all_of.hpp>
#include <boost/algorithm/cxx11/any_of.hpp>
#include <boost/algorithm/cxx11/none_of.hpp>
#include <boost/algorithm/cxx11/one_of.hpp>
#endif
#if __has_include(<boost/lambda/lambda.hpp>)
#include <boost/lambda/lambda.hpp>
#endif
#if __has_include(<boost/range/irange.hpp>)
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>
#endif
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
#include <boost/multiprecision/cpp_int.hpp>
#endif
#if __has_include(<gmpxx.h>)
#include <gmpxx.h>
#endif
using namespace std;
// constant values
const int INF32 = numeric_limits<int>::max(); //2.147483647×10^{9}:32bit整数のinf
const int inf32 = INF32 / 2;
const long long INF64 = numeric_limits<long long>::max(); //9.223372036854775807×10^{18}:64bit整数のinf
const long long inf64 = INF64 / 4;
const double EPS = numeric_limits<double>::epsilon(); //問題による
// const int MOD = 998244353; //問題による
#ifdef LOCAL
bool DEBUG = true;
#else
bool DEBUG = false;
#endif
// REP macro
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) REP2(i, 0, n)
#define REP2(i, l, r) for (long long i = (l); (i) < (long long)(r); ++(i))
#define REP3(i, l, r, s) for (long long i = (l); (i) < (long long)(r); (i) += (s))
#define rep(i, ...) OVERLOAD_REP(__VA_ARGS__, REP3, REP2, REP1)(i, __VA_ARGS__)
#define REPD1(i, n) REPD2(i, 0, n)
#define REPD2(i, l, r) for (long long i = (long long)(r) - 1; (i) >= (long long)(l); --(i))
#define REPD3(i, l, r, s) for (long long i = (long long)(r) - 1; (i) >= (long long)(l); (i) -= (s))
#define repd(i, ...) OVERLOAD_REP(__VA_ARGS__, REPD3, REPD2, REPD1)(i, __VA_ARGS__)
#define fore(i, I) for (auto& i: (I))
#define fored(i, I) for (auto& i: (I) | views::reverse)
#define all(A) A.begin(), A.end()
// for debug
#define OVERLOAD_DEBUG(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, name, ...) name
#define DUMP0 if (DEBUG) {cerr << "line: " << __LINE__;};
#define DUMP1(a) if (DEBUG) {DUMP0; cerr << ", " << #a << ": "; dump(a); cerr << endl;};
#define DUMP2(a, ...) if (DEBUG) {DUMP1(a); DUMP1(__VA_ARGS__);};
#define DUMP3(a, ...) if (DEBUG) {DUMP1(a); DUMP2(__VA_ARGS__);};
#define DUMP4(a, ...) if (DEBUG) {DUMP1(a); DUMP3(__VA_ARGS__);};
#define DUMP5(a, ...) if (DEBUG) {DUMP1(a); DUMP4(__VA_ARGS__);};
#define DUMP6(a, ...) if (DEBUG) {DUMP1(a); DUMP5(__VA_ARGS__);};
#define DUMP7(a, ...) if (DEBUG) {DUMP1(a); DUMP6(__VA_ARGS__);};
#define DUMP8(a, ...) if (DEBUG) {DUMP1(a); DUMP7(__VA_ARGS__);};
#define DUMP9(a, ...) if (DEBUG) {DUMP1(a); DUMP8(__VA_ARGS__);};
#define DUMP10(a, ...) if (DEBUG) {DUMP1(a); DUMP9(__VA_ARGS__);};
#define debug(...) OVERLOAD_DEBUG(__VA_ARGS__, DUMP10, DUMP9, DUMP8, DUMP7, DUMP6, DUMP5, DUMP4, DUMP3, DUMP2, DUMP1)(__VA_ARGS__)
#define OVERLOAD_DEBUG_LINE(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, name, ...) name
#define DUMP_LINE1(a) if (DEBUG) {cerr << ", " << #a << ": "; dump(a);};
#define DUMP_LINE2(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE1(__VA_ARGS__);};
#define DUMP_LINE3(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE2(__VA_ARGS__);};
#define DUMP_LINE4(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE3(__VA_ARGS__);};
#define DUMP_LINE5(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE4(__VA_ARGS__);};
#define DUMP_LINE6(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE5(__VA_ARGS__);};
#define DUMP_LINE7(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE6(__VA_ARGS__);};
#define DUMP_LINE8(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE7(__VA_ARGS__);};
#define DUMP_LINE9(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE8(__VA_ARGS__);};
#define DUMP_LINE10(a, ...) if (DEBUG) {DUMP_LINE1(a); DUMP_LINE9(__VA_ARGS__);};
#define debug_line(...) {DUMP0; OVERLOAD_DEBUG_LINE(__VA_ARGS__, DUMP_LINE10, DUMP_LINE9, DUMP_LINE8, DUMP_LINE7, DUMP_LINE6, DUMP_LINE5, DUMP_LINE4, DUMP_LINE3, DUMP_LINE2, DUMP_LINE1)(__VA_ARGS__); cerr << endl;}
// 省略
using ushort = unsigned short;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128_t;
using ulll = __uint128_t;
using vll = vector<ll>;
using setll = set<ll>;
using mapll = map<ll, ll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
template<typename T> using vec = vector<T>;
template<typename T> using vv = vector<vector<T>>;
using vvll = vector<vector<long long>>;
template<typename T> using vvv = vector<vector<vector<T>>>;
using str = string;
using vstr = vector<str>;
using sstr = set<str>;
using vchar = vector<char>;
using schar = set<char>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
template<typename T> using priority_queue_greater = priority_queue<T, vector<T>, greater<T>>;
// boost関連
#if __has_include(<boost/algorithm/cxx11/all_of.hpp>)
using boost::algorithm::all_of_equal;
using boost::algorithm::any_of_equal;
using boost::algorithm::none_of_equal;
using boost::algorithm::one_of_equal;
#endif
#if __has_include(<boost/lambda/lambda.hpp>)
using boost::lambda::_1;
using boost::lambda::_2;
using boost::lambda::_3;
#endif
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
using namespace boost::multiprecision;
#endif
#if __has_include(<gmpxx.h>)
#include <gmpxx.h>
using mpz = mpz_class;
#endif
// 出力ストリーム演算子
template<typename T, typename U> ostream& operator<< (ostream& os, pair<T, U>& p);
template<typename T, typename U> ostream& operator<< (ostream& os, const pair<T, U>& p);
template<typename T> ostream& operator<< (ostream& os, vector<T>& v);
template<typename T> ostream& operator<< (ostream& os, const vector<T>& v);
ostream& operator << (ostream& os, vector<string>& v);
ostream& operator << (ostream& os, const vector<string>& v);
template<typename T> ostream& operator<< (ostream& os, vector<vector<T>>& v);
template<typename T> ostream& operator<< (ostream& os, const vector<vector<T>>& v);
template<typename T> ostream& operator<< (ostream& os, vector<stack<T>>& v);
template<typename T> ostream& operator<< (ostream& os, const vector<stack<T>>& v);
template<typename T> ostream& operator<< (ostream& os, vector<queue<T>>& v);
template<typename T> ostream& operator<< (ostream& os, const vector<queue<T>>& v);
template<typename T> ostream& operator<< (ostream& os, vector<deque<T>>& v);
template<typename T> ostream& operator<< (ostream& os, const vector<deque<T>>& v);
template<typename T> ostream& operator<< (ostream& os, vector<vector<vector<T>>>& v);
template<typename T> ostream& operator<< (ostream& os, const vector<vector<vector<T>>>& v);
template<typename T> ostream& operator<< (ostream& os, set<T>& s);
template<typename T> ostream& operator<< (ostream& os, const set<T>& s);
template<typename T, typename U> ostream& operator<< (ostream& os, map<T, U>& m);
template<typename T, typename U> ostream& operator<< (ostream& os, const map<T, U>& m);
template<typename T> ostream& operator<< (ostream& os, queue<T>& que);
template<typename T> ostream& operator<< (ostream& os, const queue<T>& que);
template<typename T> ostream& operator<< (ostream& os, stack<T>& st);
template<typename T> ostream& operator<< (ostream& os, const stack<T>& st);
template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& p) { return os << "(" << p.first << ", " << p.second << ")";}
template<typename T, typename U> ostream& operator << (ostream& os, const pair<T, U>& p) { return os << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator << (ostream& os, vector<T>& v) { rep(i, v.size()) os << v[i] << ((i + 1 < (long long)v.size()) ? " " : ""); return os;}
template<typename T> ostream& operator << (ostream& os, const vector<T>& v) { rep(i, v.size()) os << v[i] << ((i + 1 < (long long)v.size()) ? " " : ""); return os;}
ostream& operator << (ostream& os, vector<string>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1) ? "\n" : ""); return os;}
ostream& operator << (ostream& os, const vector<string>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1) ? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, vector<vector<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, const vector<vector<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, vector<stack<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, const vector<stack<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, vector<queue<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, const vector<queue<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, vector<deque<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, const vector<deque<T>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1 )? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, vector<vector<vector<T>>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1) ? "\n\n": ""); return os;}
template<typename T> ostream& operator << (ostream& os, const vector<vector<vector<T>>>& v) { rep(i, v.size()) os << v[i] << ((i < (long long)v.size() - 1) ? "\n\n": ""); return os;}
template<typename T> ostream& operator << (ostream& os, set<T>& s) { for (auto it = s.begin(); it != s.end(); ++it) os << *it << ((it != --s.end()) ? " " : ""); return os;}
template<typename T> ostream& operator << (ostream& os, const set<T>& s) { for (auto it = s.begin(); it != s.end(); ++it) os << *it << ((it != --s.end()) ? " " : ""); return os;}
template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& m) { for (auto it = m.begin(); it != m.end(); ++it) os << it->first << ": " << it->second << (it != --m.end() ? "\n" : ""); return os;}
template<typename T, typename U> ostream& operator << (ostream& os, const map<T, U>& m) { for (auto it = m.begin(); it != m.end(); ++it) os << it->first << ": " << it->second << (it != --m.end() ? "\n" : ""); return os;}
template<typename T> ostream& operator << (ostream& os, queue<T>& que) { queue<T> tmp(que); while(!tmp.empty()) {os << tmp.front() << ((tmp.size() > 0)? " " : "\n"); tmp.pop();}; return os;}
template<typename T> ostream& operator << (ostream& os, const queue<T>& que) { queue<T> tmp(que); while(!tmp.empty()) {os << tmp.front() << ((tmp.size() > 0)? " " : "\n"); tmp.pop();}; return os;}
template<typename T> ostream& operator << (ostream& os, stack<T>& st) { stack<T> tmp(st); while(!tmp.empty()) {os << tmp.top() << ((tmp.size() > 0)? " " : "\n"); tmp.pop();}; return os;}
template<typename T> ostream& operator << (ostream& os, const stack<T>& st) { stack<T> tmp(st); while(!tmp.empty()) {os << tmp.top() << ((tmp.size() > 0)? " " : "\n"); tmp.pop();}; return os;}
ostream& operator<< (ostream& os, __int128_t x) {
if (x == 0) return os << '0';
if (x < 0) {os << '-'; x = -x;}
string s;
for (__int128_t y = x; y > 0; y /= 10) s += (char)('0' + y % 10);
reverse(s.begin(), s.end());
return os << s;
}
// デバッグ用
template<typename T> void dump(T a) { cerr << a;}
void dump(vector<string>& a) { cerr << '\n' << a;}
template<typename T> void dump(vector<vector<T>>& a) { cerr << '\n' << a;}
template<typename T> void dump(vector<stack<T>>& a) { cerr << '\n' << a;}
template<typename T> void dump(vector<queue<T>>& a) { cerr << '\n' << a;}
template<typename T> void dump(vector<deque<T>>& a) { cerr << '\n' << a;}
inline string YESNO(bool flag) { return flag ? "YES" : "NO";}
inline string yesno(bool flag) { return flag ? "yes" : "no";}
inline string YesNo(bool flag) { return flag ? "Yes" : "No";}
inline string POSSIBLE(bool flag) { return flag ? "POSSIBLE" : "IMPOSSIBLE";}
inline string Possible(bool flag) { return flag ? "Possible" : "Impossible";}
inline string TakahashiAoki(bool flag) { return flag ? "Takahashi" : "Aoki";}
// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き
template<typename T> inline bool chmin(T &a, const T &b) { return ((a > b) ? (a = b, true) : false);}
template<typename T> inline bool chmax(T &a, const T &b) { return ((a < b) ? (a = b, true) : false);}
#if __cplusplus > 201703L
using ranges::random_access_range;
using ranges::bidirectional_range;
using ranges::forward_range;
using ranges::input_range;
using ranges::range_value_t;
using ranges::iterator_t;
using ranges::borrowed_iterator_t;
using ranges::range_difference_t;
template <input_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool all_of(R&& r, Pred pred, Proj proj = {}) { return ranges::all_of(r, pred, proj);};
template <input_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool any_of(R&& r, Pred pred, Proj proj = {}) { return ranges::any_of(r, pred, proj);};
template <input_range R, class Proj = identity, indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> constexpr bool none_of(R&& r, Pred pred, Proj proj = {}) { return ranges::none_of(r, pred, proj);};
template <forward_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr bool is_sorted(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::is_sorted(r, comp, proj);};
template <forward_range R1, forward_range R2, class Proj1 = identity, class Proj2 = identity, indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to> constexpr bool is_permutation(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) { return is_permutation(r1, r2, pred, proj1, proj2);};
template <forward_range R, class T, class Proj = identity, indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}) { return ranges::lower_bound(r, value, comp, proj);};
template <forward_range R, class T, class Proj = identity, indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}) { return ranges::upper_bound(r, value, comp, proj);};
template <input_range R, weakly_incrementable O, class Gen> O sample(R&& r, O out, range_difference_t<R> n, Gen&& g) {return ranges::sample(r, out, n, g);};
template <input_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr range_value_t<R> max(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::max(r, comp, proj);};
template <input_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr range_value_t<R> min(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::min(r, comp, proj);};
template <input_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr ranges::minmax_result<range_value_t<R>> minmax(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::minmax(r, comp, proj);};
template <forward_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> max_element(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::max_element(r, comp, proj);};
template <forward_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr borrowed_iterator_t<R> min_element(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::min_element(r, comp, proj);};
template <forward_range R, class Proj = identity, indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> constexpr ranges::minmax_element_result<borrowed_iterator_t<R>> minmax_element(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::minmax_element(r, comp, proj);};
template <bidirectional_range R, class Comp = ranges::less, class Proj = identity> constexpr ranges::next_permutation_result<borrowed_iterator_t<R>> next_permutation(R&& r, Comp comp = {}, Proj proj = {}) {return ranges::next_permutation(r, comp, proj);};
template <bidirectional_range R, class Comp = ranges::less, class Proj = identity> constexpr ranges::prev_permutation_result<borrowed_iterator_t<R>> prev_permutation(R&& r, Comp comp = {}, Proj proj = {}) {return ranges::prev_permutation(r, comp, proj);};
template <random_access_range R, class Comp = ranges::less, class Proj = identity> constexpr borrowed_iterator_t<R> sort(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::sort(r, comp, proj);};
template <random_access_range R, class Comp = ranges::less, class Proj = identity> constexpr borrowed_iterator_t<R> stable_sort(R&& r, Comp comp = {}, Proj proj = {}) { return ranges::stable_sort(r, comp, proj);};
template <bidirectional_range R> constexpr borrowed_iterator_t<R> reverse(R&& r) { return ranges::reverse(r);};
#else
template<typename T> inline void sort(vector<T>& A) { sort(A.begin(), A.end());}
template<typename T> inline void reverse(vector<T>& A) { reverse(A.begin(), A.end());}
inline void reverse(string &s) { reverse(s.begin(), s.end());}
template<typename T> inline T min(const vector<T>& A) { return *min_element(A.begin(), A.end());}
template<typename T> inline T max(const vector<T>& A) { return *max_element(A.begin(), A.end());}
#endif
template<typename T> T accumulate(vector<T> A) { return accumulate(A.begin(), A.end(), T(0));}
template<typename T> inline size_t min_index(const vector<T>& A) { return distance(A.begin(), min_element(A.begin(), A.end()));}
template<typename T> inline size_t max_index(const vector<T>& A) { return distance(A.begin(), max_element(A.begin(), A.end()));}
// math関係
inline long long min(long long x, int y) {return min(x, (long long)y);}
inline long long min(int x, long long y) {return min((long long)x, y);}
inline long long max(long long x, int y) {return max(x, (long long)y);}
inline long long max(int x, long long y) {return max((long long)x, y);}
inline long long ceil(long long x, long long y) { return x / y + (x % y > 0);}
inline long long floor(long long x, long long y) { return x / y - (x % y < 0);}
pair<long long, long long> divmod(long long x, long long y) {return ((x >= 0) ? pll(x / y, x % y) : pll((x - y + 1) / y, (x % y + y) % y));}
template <typename T = unsigned long long> inline T binpow(T x, T n) { T ret = 1; while (n) {if (n & 1) ret *= x; x *= x; n >>= 1;} return ret; }
template <typename T = unsigned long long> inline T binpow(T x, T n, T m) { T ret = 1; while (n) {if (n & 1) ret = (ret * x) % m; x = (x * x) % m; n >>= 1;} return ret; }
// mod. m での a の逆元 a^{-1} を計算する
template<typename T> T modinv(T a, T m) {
T b = m, u = 1, v = 0;
while (b) { T t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
u %= m;
if (u < 0) u += m;
return u;
}
// combinationを求める
long long nCr(long long n, long long k, long long m = 0) {
if (n < k) return 0;
if (n - k < k) k = n - k;
long long ret = 1;
rep(i, k) {
ret *= (n - i);
if (m > 0) ret %= m;
}
rep(i, 1, k + 1) {
if (m > 0) {
ret *= modinv(i, m);
ret %= m;
}
else ret /= i;
}
return ret;
}
// 最大公約数を求める
long long gcd(const vector<long long> &A) {
long long ret = 0;
rep(i, A.size()) ret = gcd(ret, A[i]);
return ret;
}
// 最小公倍数を求める
long long lcm(const vector<long long> &A, const long long m = 0) {
long long ret = 1;
rep(i, A.size()) { ret = lcm(ret, A[i]); if (m > 0) ret %= m;}
return ret;
}
// 拡張ユークリッドの互除法
tuple<long long, long long, long long> extGCD(long long a, long long b) {
if (b == 0) return {a, 1, 0};
auto [g, x, y] = extGCD(b, a % b);
return {g, y, x - (a / b) * y};
}
// 分数比較
inline bool is_greater(long long p, long long q, long long r, long long s) { return __int128_t(p) * s > __int128_t(q) * r;}
inline bool is_greater_or_equal(long long p, long long q, long long r, long long s) { return __int128_t(p) * s >= __int128_t(q) * r;}
inline bool is_less(long long p, long long q, long long r, long long s) { return __int128_t(p) * s < __int128_t(q) * r;}
inline bool is_less_or_equal(long long p, long long q, long long r, long long s) { return __int128_t(p) * s <= __int128_t(q) * r;}
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
inline bool is_greater(__int128_t p, __int128_t q, __int128_t r, __int128_t s) { return int256_t(p) * s > int256_t(q) * r;}
inline bool is_greater_or_equal(__int128_t p, __int128_t q, __int128_t r, __int128_t s) { return int256_t(p) * s >= int256_t(q) * r;}
inline bool is_less(__int128_t p, __int128_t q, __int128_t r, __int128_t s) { return int256_t(p) * s < int256_t(q) * r;}
inline bool is_less_or_equal(__int128_t p, __int128_t q, __int128_t r, __int128_t s) { return int256_t(p) * s <= int256_t(q) * r;}
#endif
// string関係
inline string lltos(long long x) { return to_string(x);}
inline int ctoi(char x) { return int(x - '0');}
inline char itoc(int x) { return (char)(x + '0');}
#if __has_include(<boost/algorithm/string.hpp>)
inline string to_upper(string& S) { return boost::to_upper_copy(S);}
inline string to_lower(string& S) { return boost::to_lower_copy(S);}
#endif
inline bool is_lower(char c) { return (c >= 'a') and (c <= 'z');}
inline bool is_upper(char c) { return (c >= 'A') and (c <= 'Z');}
inline char to_upper(char c) { if (is_upper(c)) return c; else return c + 'A' - 'a';}
inline char to_lower(char c) { if (is_lower(c)) return c; else return c + 'a' - 'A';}
inline string zero_padding(string N, long long width) {
stringstream ss;
ss << setw(width) << setfill('0') << N;
return ss.str();
}
inline string zero_padding(long long N, long long width) { return zero_padding(lltos(N), width);}
inline string to_n_base(long long x, long long base) {
assert(2 <= base and base <= 36);
if (x == 0) return "0";
string ret;
for (; x > 0; x /= base) ret += (((x % base) < 10) ? '0' + (x % base) : 'a' + (x % base) - 10);
reverse(ret);
return ret;
}
inline long long to_decimal(string S, long long base) {
assert(2 <= base and base <= 36);
long long ret = 0, x = 1;
repd(i, S.size()) {
ret += (long long)(('0' <= S[i] and S[i] <= '9') ? S[i] - '0' : (('a' <= S[i] and S[i] <= 'z') ? S[i] = 'a' + 10 : S[i] - 'A' + 10)) * x;
x *= base;
}
return ret;
}
bool is_palindrome(const string& S) {
rep(i, S.size() / 2) if (S[i] != S[S.size() - i - 1]) return false;
return true;
}
template<class T = long long> inline pair<T, T> DRUL(T y, T x, char c) { return {((c == 'D') ? y + 1 : ((c == 'U') ? y - 1 : y)), ((c == 'R') ? x + 1 : ((c == 'L') ? x - 1 : x))};}
template <typename T> long long bubble_sort(vector<T> &A) {
ll ret = 0;
rep(i, A.size() - 1) rep(j, A.size() - 1) if (A[j] > A[j + 1]) {
swap(A[j], A[j + 1]);
++ret;
}
return ret;
}
template<typename T> vector<T> compress(const vector<T> &A, bool unique_id = false) {
long long N = A.size();
vector<pair<T, long long>> B;
rep(i, N) B.emplace_back(A[i], i);
sort(B.begin(), B.end());
vector<T> C(N);
ll count = 0;
rep(i, N) {
C[B[i].second] = count;
if (unique_id)++count;
else if (i < N - 1 and B[i].first != B[i + 1].first) ++count;
}
return C;
}
// bit関係
bool bit_test(long long x, long long pos) { return (x >> pos) & 1ll; }
long long bit_set(long long x, long long pos, bool flg) { return flg ? (x | (1ll << pos)) : (x & ~(1ll << pos)); }
long long bit_flip(long long x, long long pos) { return x ^ (1ll << pos); }
#if __cplusplus > 201703L
long long bit_count(long long x) { return popcount((ull)x); }
#else
long long bit_count(long long x) { return __builtin_popcountll(x); }
#endif
// 配列関係
// キー以上の最小の要素を見つけるイテレータを返す関数
template <typename T> inline typename vector<T>::iterator find_greater_than_or_equal(vector<T>& v, T key) { return lower_bound(v.begin(), v.end(), key); }
template <typename T> inline typename vector<T>::iterator find_greater_than_or_equal(typename vector<T>::iterator begin, typename vector<T>::iterator end, T key) { return lower_bound(begin, end, key); }
template <typename T> inline typename set<T>::iterator find_greater_than_or_equal(set<T>& st, T key) { return st.lower_bound(key); }
// キーを超える最小の要素を見つけるイテレータを返す関数
template <typename T> inline typename vector<T>::iterator find_greater_than(vector<T>& v, T key) { return upper_bound(v.begin(), v.end(), key); }
template <typename T> inline typename vector<T>::iterator find_greater_than(typename vector<T>::iterator begin, typename vector<T>::iterator end, T key) { return upper_bound(begin, end, key); }
template <typename T> inline typename set<T>::iterator find_greater_than(set<T>& st, T key) { return st.upper_bound(key); }
// キー以下の最大の要素を見つけるイテレータを返す関数, ない場合はendを返す
template <typename T> inline typename vector<T>::iterator find_less_than_or_equal(vector<T>& v, T key) { auto it = upper_bound(v.begin(), v.end(), key); return it == v.begin() ? v.end() : --it;}
template <typename T> inline typename vector<T>::iterator find_less_than_or_equal(typename vector<T>::iterator begin, typename vector<T>::iterator end, T key) { auto it = upper_bound(begin, end, key); return it == begin ? end : --it;}
template <typename T> inline typename set<T>::iterator find_less_than_or_equal(set<T>& st, T key) { auto it = st.upper_bound(key); return it == st.begin() ? st.end() : --it;}
// キー未満の最大の要素を見つけるイテレータを返す関数, ない場合はendを返す
template <typename T> inline typename vector<T>::iterator find_less_than(vector<T>& v, T key) { auto it = lower_bound(v.begin(), v.end(), key); return it == v.begin() ? v.end() : --it; }
template <typename T> inline typename vector<T>::iterator find_less_than(typename vector<T>::iterator begin, typename vector<T>::iterator end, T key) { auto it = lower_bound(begin, end, key); return it == begin ? end : --it; }
template <typename T> inline typename set<T>::iterator find_less_than(set<T>& st, T key) { auto it = st.lower_bound(key); return it == st.begin() ? st.end() : --it;}
template <typename T> auto operator+(const vector<T>& A, const T x) { vector<T> ret(A.size()); rep(i, A.size()) ret[i] = A[i] + x; return ret; }
template <typename T> auto operator-(const vector<T>& A, const T x) { vector<T> ret(A.size()); rep(i, A.size()) ret[i] = A[i] - x; return ret; }
template <typename T> auto operator*(const vector<T>& A, const T x) { vector<T> ret(A.size()); rep(i, A.size()) ret[i] = A[i] * x; return ret; }
template <typename T> auto operator/(const vector<T>& A, const T x) { vector<T> ret(A.size()); rep(i, A.size()) ret[i] = A[i] / x; return ret; }
template <typename T> auto operator%(const vector<T>& A, const T x) { vector<T> ret(A.size()); rep(i, A.size()) ret[i] = A[i] % x; return ret; }
template <typename T> auto binpow(const vector<T>& A, const T x) { vector<T> ret(A.size()); rep(i, A.size()) ret[i] = binpow(A[i], x); return ret; }
template <typename R> auto& operator++(R& a) { for (auto& x : a) ++x; return a; }
template <typename R> auto operator++(R& a, int) { auto temp = a; for (auto& x : a) x++; return temp; }
template <typename R> auto& operator--(R& a) { for (auto& x : a) --x; return a; }
template <typename R> auto operator--(R& a, int) { auto temp = a; for (auto& x : a) x--; return temp; }
template <typename T, typename U> auto operator+(const pair<T, U>& p, const T x) { return pair<T, U>(p.first + x, p.second + x); }
template <typename T, typename U> auto operator-(const pair<T, U>& p, const T x) { return pair<T, U>(p.first - x, p.second - x); }
template <typename T, typename U> auto operator*(const pair<T, U>& p, const T x) { return pair<T, U>(p.first * x, p.second * x); }
template <typename T, typename U> auto operator/(const pair<T, U>& p, const T x) { return pair<T, U>(p.first / x, p.second / x); }
template <typename T, typename U> auto operator%(const pair<T, U>& p, const T x) { return pair<T, U>(p.first % x, p.second % x); }
template <typename T, typename U> auto binpow(const pair<T, U>& p, const T x) { return pair<T, U>(binpow(p.first, x), binpow(p.second, x)); }
template <typename T, typename U> auto operator+(const pair<T, U>& p, const pair<T, U>& q) { return pair<T, U>(p.first + q.first, p.second + q.second); }
template <typename T, typename U> auto operator-(const pair<T, U>& p, const pair<T, U>& q) { return pair<T, U>(p.first - q.first, p.second - q.second); }
template <typename T, typename U> auto operator*(const pair<T, U>& p, const pair<T, U>& q) { return pair<T, U>(p.first * q.first, p.second * q.second); }
template <typename T, typename U> auto operator/(const pair<T, U>& p, const pair<T, U>& q) { return pair<T, U>(p.first / q.first, p.second / q.second); }
template <typename T, typename U> auto operator%(const pair<T, U>& p, const pair<T, U>& q) { return pair<T, U>(p.first % q.first, p.second % q.second); }
template <typename T, typename U> auto& operator++(pair<T, U>& p) { ++p.first; ++p.second; return p; }
template <typename T, typename U> auto operator++(pair<T, U>& p, int) { auto temp = p; ++p.first; ++p.second; return temp; }
template <typename T, typename U> auto& operator--(pair<T, U>& p) { --p.first; --p.second; return p; }
template <typename T, typename U> auto operator--(pair<T, U>& p, int) { auto temp = p; --p.first; --p.second; return temp; }
template<typename T, typename U> vector<pair<T, U>> to_pair(const vector<T>& vec1, const vector<U>& vec2) {
size_t n = min(vec1.size(), vec2.size());
vector<pair<T, U>> result(n);
for(size_t i = 0; i < n; ++i) result.emplace_back(vec1[i], vec2[i]);
return result;
}
bool compare_frac(pair<long long, long long> a, pair<long long, long long> b, function<bool(__int128_t, __int128_t)> comp) { return comp((__int128_t)a.first * b.second, (__int128_t)a.second * b.first);}
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
bool compare_frac(pair<__int128_t, __int128_t> a, pair<__int128_t, __int128_t> b, function<bool(cpp_int, cpp_int)> comp) { return comp(a.first * b.second, a.second * b.first);}
#endif
namespace _hash61 {
const unsigned long long MOD = (1ULL << 61) - 1;
const unsigned long long MASK30 = (1ULL << 30) - 1;
const unsigned long long MASK31 = (1ULL << 31) - 1;
const unsigned long long MASK61 = MOD;
unsigned long long set_base(unsigned long long Max = 127, unsigned long long MOD = (1ULL << 61) - 1, unsigned long long root = 37) {
random_device rd;
mt19937_64 gen(rd());
uniform_int_distribution<unsigned long long> dist(1, numeric_limits<unsigned long long>::max());
unsigned long long ret;
while (true) {
unsigned long long k = dist(gen);
ret = binpow(root, k, MOD);
if (ret > Max) break;
}
return ret;
}
unsigned long long calc_mul(unsigned long long a, unsigned long long b) {
unsigned long long au = a >> 31;
unsigned long long ad = a & MASK31;
unsigned long long bu = b >> 31;
unsigned long long bd = b & MASK31;
unsigned long long mid = ad * bu + au * bd;
unsigned long long midu = mid >> 30;
unsigned long long midd = mid & MASK30;
return au * bu * 2 + midu + (midd << 31) + ad * bd;
}
unsigned long long calc_mod(unsigned long long x) {
unsigned long long xu = x >> 61;
unsigned long long xd = x & MASK61;
unsigned long long res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
}
unsigned long long binpow(unsigned long long x, unsigned long long n) {
unsigned long long ret = 1;
while (n > 0) {
if (n & 1) ret = calc_mod(calc_mul(ret, x));
x = calc_mod(calc_mul(x, x));
n >>= 1;
}
return ret;
}
unsigned long long modinv(unsigned long long a) { return binpow(a, MOD - 2);}
static const unsigned long long base = set_base();
const unsigned long long base_inv = modinv(base);
}
struct Hash61 {
unsigned long long hash, hash_rev;
unsigned long long pow, pow_inv;
long long N;
Hash61() {
init();
}
Hash61(string& S) {
if (S.size() > 0) set(S);
}
Hash61(char c) {
string S(1, c);
set(S);
}
void init() {
N = 0;
hash = 0;
hash_rev = 0;
pow = 1;
pow_inv = 1;
}
void set(char c) {
string S = string(1, c);
set(S);
}
void set(string& S) {
init();
N = S.size();
rep(i, S.size()) {
unsigned long long c = S[i];
hash = _hash61::calc_mod(_hash61::calc_mul(hash, _hash61::base) + c);
pow = _hash61::calc_mod(_hash61::calc_mul(pow, _hash61::base));
pow_inv = _hash61::calc_mod(_hash61::calc_mul(pow_inv, _hash61::base_inv));
}
repd(i, S.size()) {
unsigned long long c = S[i];
hash_rev = _hash61::calc_mod(_hash61::calc_mul(hash_rev, _hash61::base) + c);
}
}
bool is_palindrome() {
return hash == hash_rev;
}
Hash61 reverse() {
Hash61 ret;
ret.hash = hash_rev;
ret.hash_rev = hash;
ret.pow = pow;
ret.pow_inv = pow_inv;
ret.N = N;
return ret;
}
operator unsigned long long() const {
return hash;
}
friend Hash61 operator+ (const Hash61 &lhs, const Hash61 &rhs) {
return Hash61(lhs) += rhs;
}
Hash61& operator+= (const Hash61 &other) noexcept {
hash = _hash61::calc_mod(_hash61::calc_mul(hash, other.pow) + other.hash);
hash_rev = _hash61::calc_mod(_hash61::calc_mul(other.hash_rev, pow) + hash_rev);
pow = _hash61::calc_mod(_hash61::calc_mul(pow, other.pow));
pow_inv = _hash61::calc_mod(_hash61::calc_mul(pow_inv, other.pow_inv));
N += other.N;
return *this;
}
bool operator< (const Hash61 &other) const {
return (N < other.N) && (hash < other.hash);
}
bool operator== (const Hash61 &other) const noexcept {
return (N == other.N) && (hash == other.hash);
}
friend ostream& operator<<(ostream &os, const Hash61& h) {
return os << h.hash;
}
};
struct BinaryIndexedTree {
long long N, _N, height;
string S;
vector<unsigned long long> bit, bit_rev;
vector<unsigned long long> pow, pow_inv;
BinaryIndexedTree(long long n): _N(n), S(n, 0) {
init();
}
BinaryIndexedTree(const string &S): _N(S.size()), S(S) {
init();
rep(i, _N) set(i, S[i]);
}
void init() {
N = 1;
height = 1;
while (N < (_N + 1)) {
N *= 2;
++height;
}
bit.assign(N + 1, 0);
bit_rev.assign(N + 1, 0);
pow.assign(N + 1, 1);
pow_inv.assign(N + 1, 1);
rep(i, N) {
pow[i + 1] = _hash61::calc_mod(_hash61::calc_mul(pow[i], _hash61::base));
pow_inv[i + 1] = _hash61::calc_mod(_hash61::calc_mul(pow_inv[i], _hash61::base_inv));
}
}
// 位置p (0-indexed)をxにする
void set(long long p, char c) {
assert(0 <= p and p < _N);
unsigned long long x = _hash61::calc_mod(_hash61::MOD - S[p] + c);
unsigned long long hash = _hash61::calc_mod(_hash61::calc_mul(x, pow[N - 1 - p]));
unsigned long long hash_rev = _hash61::calc_mod(_hash61::calc_mul(x, pow[p]));
S[p] = c;
add(bit, p, hash);
add(bit_rev, p, hash_rev);
}
// 半開区間[0, r) (0-indexed)の総和を求める
Hash61 sum(long long r) {
return sum(0, r);
}
// 半開区間[l, r) (0-indexed)の総和を求める
Hash61 sum(long long l, long long r) {
assert(0 <= l and l <= r and r <= _N);
if (l == r) return 0;
Hash61 hash;
hash.N = r - l;
hash.hash = _hash61::calc_mod(_hash61::calc_mul(_hash61::calc_mod(sum(bit, r) + _hash61::MOD - sum(bit, l)), pow_inv[N - r]));
hash.hash_rev = _hash61::calc_mod(_hash61::calc_mul(_hash61::calc_mod(sum(bit_rev, r) + _hash61::MOD - sum(bit_rev, l)), pow_inv[l]));
hash.pow = pow[r - l];
hash.pow_inv = pow_inv[r - l];
return hash;
}
// 半開区間[p, p + 1) (0-indexed)の値を求める
Hash61 get(long long p) {
assert(0 <= p and p < _N);
return Hash61(S[p]);
}
private:
// 半開区間[0, r) (0-indexed)の総和を求める
unsigned long long sum(vector<unsigned long long> &bit, long long r) {
assert(0 <= r and r <= _N);
if (r == 0) return 0;
unsigned long long ret = 0;
for (int idx = r; idx > 0; idx -= (idx & -idx)) {
ret = _hash61::calc_mod(ret + bit[idx]);
}
return ret;
}
// 位置p (0-indexed)にxを加える
void add(vector<unsigned long long> &bit, long long p, unsigned long long x) {
assert(0 <= p and p <= _N);
++p; // 1-indexed
for (int idx = p; idx < N; idx += (idx & -idx)) {
bit[idx] = _hash61::calc_mod(bit[idx] + x);
}
}
};
int main() {
ll N, L, Q;
cin >> N >> L >> Q;
vector<string> S(N);
rep(i, N) cin >> S[i];
vector<BinaryIndexedTree> bit(N, L);
rep(i, N) rep(j, L) bit[i].set(j, S[i][j]);
while (Q--) {
ll q;
cin >> q;
if (q == 1) {
ll k;
char c, d;
cin >> k >> c >> d;
--k;
rep(i, N) {
if (S[i][k] != c) continue;
S[i][k] = d;
bit[i].set(k, d);
}
}
else {
string t;
cin >> t;
Hash61 hs(t);
ll ans = 0;
rep(i, N) {
if (bit[i].sum(t.size()).hash_rev == hs.hash_rev) ++ans;
}
cout << ans << endl;
}
}
// cout << fixed << setprecision(10); // 小数点以下を10桁表示，許容誤差が1e-N以下の時はN+1に変更すること(16桁以上はlong double)
// cout << ans << endl;
// cout << (ans < inf64 ? ans : -1) << endl;
// cout << YesNo(ans) << endl;
// rep(i, N) cout << (ans[i] < inf64 ? ans[i] : -1) << endl;
return 0;
}