結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
|
提出日時 | 2024-05-19 19:37:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 882 ms / 4,000 ms |
コード長 | 1,620 bytes |
コンパイル時間 | 2,235 ms |
コンパイル使用メモリ | 208,612 KB |
最終ジャッジ日時 | 2025-02-21 16:04:24 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/modint> using namespace atcoder; using namespace std; using mint = modint; using ll = long long; #include <atcoder/fenwicktree> int main() { int N, L, Q;cin >> N >> L >> Q; mint::set_mod((ll)(1e9 + 7)); vector<fenwick_tree<mint>> RLH; int K = 5000; vector<mint> E(K + 1, 0); E[0] = 1; mint R = 998244353; for (int i = 1;i <= K;i++) E[i] = E[i - 1] * R; vector<vector<int>> S(N, vector<int>(L + 1, -1)); for (int i = 0;i < N;i++) { string s;cin >> s; mint now = 1; fenwick_tree<mint> BIT(L + 1); for (int j = 1;j <= L;j++) { int nc = s[j - 1] - 'a'; S[i][j] = nc; mint t = nc * E[j - 1]; BIT.add(j, t); } RLH.push_back(BIT); } while (Q--) { int op;cin >> op; if (op == 2) { string t;cin >> t; mint rlh = 0; int l = t.size(); for (int i = 0;i < l;i++) { rlh += (t[i] - 'a') * E[i]; } int ans = 0; for (int i = 0;i < N;i++) { mint bits = RLH[i].sum(0, l + 1); if (bits == rlh) ans++; } cout << ans << endl; } else { int k;char C, D;cin >> k >> C >> D; int c = C - 'a';int d = D - 'a'; for (int i = 0;i < N;i++) { if (S[i][k] != c) continue; S[i][k] = d; RLH[i].add(k, -(c * E[k - 1])); RLH[i].add(k, (d * E[k - 1])); } } } }