結果
問題 |
No.2761 Substitute and Search
|
ユーザー |
|
提出日時 | 2024-05-26 14:05:04 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 745 ms / 4,000 ms |
コード長 | 1,317 bytes |
コンパイル時間 | 9,401 ms |
コンパイル使用メモリ | 351,556 KB |
実行使用メモリ | 39,296 KB |
最終ジャッジ日時 | 2024-12-20 20:16:19 |
合計ジャッジ時間 | 15,023 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using mint=modint998244353; using S=mint; S op(S a,S b){ return (a+b); } S e(){ return mint(0); } int main(){ ll n,l,q; cin>>n>>l>>q; vector<string> s(n); for(ll i=0;i<n;i++){ cin>>s[i]; } mint base=rand(); vector<segtree<S,op,e>> seg; vector<mint> basepow(l); basepow[0]=mint(1); for(ll i=0;i<l-1;i++){ basepow[i+1]=basepow[i]*base; } for(ll i=0;i<n;i++){ vector<mint> v(l); for(ll j=0;j<l;j++){ v[j]=mint(s[i][j]-'a')*basepow[j]; } segtree<S,op,e> seg_(v); seg.push_back(seg_); } while(q--){ ll ty; cin>>ty; if(ty==1){ ll k; cin>>k; k--; char c,d; cin>>c>>d; for(ll i=0;i<n;i++){ if(s[i][k]==c){ s[i][k]=d; seg[i].set(k,mint(d-'a')*basepow[k]); } } }else{ string t; cin>>t; mint num=mint(0); ll ans=0; for(ll i=0;i<(ll)t.size();i++){ num+=mint(t[i]-'a')*basepow[i]; } for(ll i=0;i<n;i++){ if(num==seg[i].prod(0,(ll)t.size())){ ans++; } } cout<<ans<<endl; } } }