結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
![]() |
提出日時 | 2024-05-20 19:46:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 844 ms / 4,000 ms |
コード長 | 1,927 bytes |
コンパイル時間 | 3,907 ms |
コンパイル使用メモリ | 259,468 KB |
最終ジャッジ日時 | 2025-02-21 16:19:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using mint = modint998244353; unsigned int xorshift() { static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned int t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } mint op(mint a, mint b) { return a + b; } mint e() { return mint(0); } int main() { int n, l, q; cin >> n >> l >> q; vector<string> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } mint b = mint(xorshift()); vector<mint> pows(3010); pows[0] = mint(1); for (int i = 1; i < 3010; i++) { pows[i] = pows[i - 1] * b; } vector<segtree<mint, op, e>> seg(n, segtree<mint, op, e>(l)); for (int i = 0; i < n; i++) { for (int j = 0; j < l; j++) { mint x = mint(s[i][j] - 'a' + 1); mint h = pows[j] * x; seg[i].set(j, h); } } while (q--) { int t; cin >> t; if (t == 1) { int k; char c, d; cin >> k >> c >> d; k--; mint x = mint(d - 'a' + 1); for (int i = 0; i < n; i++) { if (s[i][k] == c) { mint h = pows[k] * x; seg[i].set(k, h); s[i][k] = d; } } } else { string pre; cin >> pre; int len = pre.size(); mint h = mint(0); for (int i = 0; i < len; i++) { mint x = mint(pre[i] - 'a' + 1); h += pows[i] * x; } int ans = 0; for (int i = 0; i < n; i++) { if (seg[i].prod(0, len) == h) { ans++; } } cout << ans << endl; } } }