結果
| 問題 | No.2761 Substitute and Search |
| ユーザー |
 rniya
|
| 提出日時 | 2024-05-17 22:07:54 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2,826 ms / 4,000 ms |
| コード長 | 5,823 bytes |
| コンパイル時間 | 8,283 ms |
| コンパイル使用メモリ | 270,676 KB |
| 最終ジャッジ日時 | 2025-02-21 14:52:59 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
コンパイルメッセージ
main.cpp: In function 'std::ostream& hash_impl::operator<<(std::ostream&, const modint&)':
main.cpp:95:90: warning: no return statement in function returning non-void [-Wreturn-type]
95 | friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; }
| ^
ソースコード
#include <bits/stdc++.h>#ifdef LOCAL#include <debug.hpp>#else#define debug(...) void(0)#endiftemplate <class T> std::istream& operator>>(std::istream& is, std::vector<T>& v) {for (auto& e : v) {is >> e;}return is;}template <class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {for (std::string_view sep = ""; const auto& e : v) {os << std::exchange(sep, " ") << e;}return os;}template <class T, class U = T> bool chmin(T& x, U&& y) {return y < x and (x = std::forward<U>(y), true);}template <class T, class U = T> bool chmax(T& x, U&& y) {return x < y and (x = std::forward<U>(y), true);}template <class T> void mkuni(std::vector<T>& v) {std::ranges::sort(v);auto result = std::ranges::unique(v);v.erase(result.begin(), result.end());}template <class T> int lwb(const std::vector<T>& v, const T& x) {return std::distance(v.begin(), std::ranges::lower_bound(v, x));}#include <atcoder/segtree>namespace hash_impl {static constexpr unsigned long long mod = (1ULL << 61) - 1;struct modint {modint() : _v(0) {}modint(unsigned long long v) {v = (v >> 61) + (v & mod);if (v >= mod) v -= mod;_v = v;}unsigned long long val() const { return _v; }modint& operator+=(const modint& rhs) {_v += rhs._v;if (_v >= mod) _v -= mod;return *this;}modint& operator-=(const modint& rhs) {if (_v < rhs._v) _v += mod;_v -= rhs._v;return *this;}modint& operator*=(const modint& rhs) {__uint128_t t = __uint128_t(_v) * rhs._v;t = (t >> 61) + (t & mod);if (t >= mod) t -= mod;_v = t;return *this;}modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); }modint operator-() const { return modint() - *this; }modint pow(long long n) const {assert(0 <= n);modint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}modint inv() const { return pow(mod - 2); }friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; }friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; }friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; }friend modint operator/(const modint& lhs, const modint& rhs) { return modint(lhs) /= rhs; }friend bool operator==(const modint& lhs, const modint& rhs) { return lhs._v == rhs._v; }friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs._v != rhs._v; }friend std::ostream& operator<<(std::ostream& os, const modint& rhs) { os << rhs._v; }private:unsigned long long _v;};uint64_t generate_base() {std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());std::uniform_int_distribution<uint64_t> rand(2, mod - 1);return rand(mt);}modint base(generate_base());std::vector<modint> power{1};modint get_pow(int n) {if (n < int(power.size())) return power[n];int m = power.size();power.resize(n + 1);for (int i = m; i <= n; i++) power[i] = power[i - 1] * base;return power[n];}}; // namespace hash_implstruct Hash {using mint = hash_impl::modint;mint x;int len;Hash() : x(0), len(0) {}Hash(mint x, int len) : x(x), len(len) {}Hash& operator+=(const Hash& rhs) {x = x * hash_impl::get_pow(rhs.len) + rhs.x;len += rhs.len;return *this;}Hash operator+(const Hash& rhs) { return *this += rhs; }bool operator==(const Hash& rhs) { return x == rhs.x and len == rhs.len; }};struct ReversibleHash {using mint = hash_impl::modint;mint x, rx;int len;ReversibleHash() : x(0), rx(0), len(0) {}ReversibleHash(mint x) : x(x), rx(x), len(1) {}ReversibleHash(mint x, mint rx, int len) : x(x), rx(rx), len(len) {}ReversibleHash rev() const { return ReversibleHash(rx, x, len); }ReversibleHash operator+=(const ReversibleHash& rhs) {x = x * hash_impl::get_pow(rhs.len) + rhs.x;rx = rx + rhs.rx * hash_impl::get_pow(len);len += rhs.len;return *this;}ReversibleHash operator+(const ReversibleHash& rhs) { return *this += rhs; }bool operator==(const ReversibleHash& rhs) { return x == rhs.x and rx == rhs.rx and len == rhs.len; }};using ll = long long;using namespace std;Hash op(Hash l, Hash r) { return l + r; }Hash e() { return Hash(); }int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout << fixed << setprecision(15);int N, L, Q;cin >> N >> L >> Q;vector<string> S(N);cin >> S;vector<atcoder::segtree<Hash, op, e>> seg(N, atcoder::segtree<Hash, op, e>(L));for (int i = 0; i < N; i++) {for (int j = 0; j < L; j++) {seg[i].set(j, Hash(S[i][j], 1));}}for (; Q--;) {int type;cin >> type;if (type == 1) {int k;char c, d;cin >> k >> c >> d;k--;for (int i = 0; i < N; i++) {if (S[i][k] == c) {S[i][k] = d;seg[i].set(k, Hash(S[i][k], 1));}}} else {string t;cin >> t;int n = t.size();Hash sum = Hash();for (int i = 0; i < n; i++) sum += Hash(t[i], 1);int ans = 0;for (int i = 0; i < N; i++) ans += (seg[i].prod(0, n) == sum);cout << ans << '\n';}}return 0;}