結果

問題 No.2761 Substitute and Search
ユーザー KudeKude
提出日時 2024-05-17 22:46:22
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,233 ms / 4,000 ms
コード長 3,662 bytes
コンパイル時間 2,953 ms
コンパイル使用メモリ 282,752 KB
実行使用メモリ 142,724 KB
最終ジャッジ日時 2024-05-17 22:46:46
合計ジャッジ時間 10,947 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
7,552 KB
testcase_01 AC 6 ms
7,364 KB
testcase_02 AC 5 ms
7,288 KB
testcase_03 AC 5 ms
7,424 KB
testcase_04 AC 593 ms
142,656 KB
testcase_05 AC 1,233 ms
142,620 KB
testcase_06 AC 226 ms
142,496 KB
testcase_07 AC 742 ms
142,604 KB
testcase_08 AC 222 ms
142,596 KB
testcase_09 AC 764 ms
142,608 KB
testcase_10 AC 198 ms
142,648 KB
testcase_11 AC 767 ms
142,604 KB
testcase_12 AC 486 ms
142,724 KB
testcase_13 AC 493 ms
142,592 KB
testcase_14 AC 473 ms
142,656 KB
testcase_15 AC 475 ms
142,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;


class mint61 {
  using ull = unsigned long long;
  using ui128 = __uint128_t;

 public:
  static constexpr unsigned long long mod = (1ULL << 61) - 1;
  ull v = 0;
  constexpr mint61() {}
  explicit constexpr mint61(ull x) {
    v = (x >> 61) + (x & mod);
    if (v >= mod) v -= mod;
  }
  static constexpr mint61 raw(ull x) {
    mint61 res;
    res.v = x;
    return res;
  }
  friend constexpr mint61 operator+(mint61 lhs, mint61 rhs) {
    auto res = lhs.v + rhs.v;
    return raw(res < mod ? res : res - mod);
  }
  friend constexpr mint61 operator-(mint61 lhs, mint61 rhs) {
    return raw(lhs.v >= rhs.v ? lhs.v - rhs.v : mod + lhs.v - rhs.v);
  }
  static constexpr ull multiply_loose_mod(mint61 lhs, mint61 rhs) {
    // ab = q(m+1)+r = qm+q+r
    // q+r = ab-qm = ab-floor(ab/(m+1))m < ab-(ab/(m+1)-1)m = ab/(m+1)+m <=
    // (m-1)^2/(m+1)+m = 2m-3+4/(m+1)
    auto mul = ui128(lhs.v) * rhs.v;
    return ull(mul >> 61) + ull(mul & mod);
  }
  friend constexpr mint61 operator*(mint61 lhs, mint61 rhs) {
    auto res = multiply_loose_mod(lhs, rhs);
    return raw(res < mod ? res : res - mod);
  }
  mint61& operator+=(mint61 rhs) { return *this = *this + rhs; }
  mint61& operator-=(mint61 rhs) { return *this = *this - rhs; }
  mint61& operator*=(mint61 rhs) { return *this = *this * rhs; }
  friend constexpr bool operator==(const mint61& lhs, const mint61& rhs) {
    return lhs.v == rhs.v;
  }
  friend ostream& operator<<(ostream& os, mint61 x) { return os << x.v; }
};

std::mt19937 RNG(std::chrono::system_clock::now().time_since_epoch().count());
unsigned long long RULL(unsigned long long L, unsigned long long R) {
  assert(L < R);
  return std::uniform_int_distribution<unsigned long long>(L, R - 1)(RNG);
}

const mint61 B = mint61::raw(RULL(1, mint61::mod));

constexpr int MXSIZE = 500010;
mint61 powB[MXSIZE + 1];
auto init_Bs = [] {
  powB[0] = mint61::raw(1);
  for (int i = 0; i < MXSIZE; i++) powB[i + 1] = powB[i] * B;
  return false;
}();

struct S {
  int cnt;
  mint61 v;
};

S op(S x, S y) {
  return S{x.cnt + y.cnt, x.v * powB[y.cnt] + y.v};
}
S e() { return {0, mint61()}; }

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, l, q;
  cin >> n >> l >> q;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  vector<segtree<S, op, e>> seg;
  rep(i, n) {
    seg.emplace_back([&]() {
      vector<S> init(l);
      rep(j, l) init[j] = S{1, mint61::raw(s[i][j])};
      return init;
    }());
  }
  rep(_, q) {
    int op;
    cin >> op;
    if (op == 1) {
      int k;
      char c, d;
      cin >> k >> c >> d;
      k--;
      rep(i, n) if (s[i][k] == c) {
        s[i][k] = d;
        seg[i].set(k, S{1, mint61::raw(s[i][k])});
      }
    } else {
      string t;
      cin >> t;
      mint61 h;
      int m = t.size();
      rep(j, m) h = B * h + mint61::raw(t[j]);
      int ans = 0;
      rep(i, n) ans += seg[i].prod(0, m).v == h;
      cout << ans << '\n';
    }
  }
}
0