結果
問題 | No.2761 Substitute and Search |
ユーザー |
|
提出日時 | 2024-05-26 14:48:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 827 ms / 4,000 ms |
コード長 | 1,329 bytes |
コンパイル時間 | 8,578 ms |
コンパイル使用メモリ | 351,588 KB |
実行使用メモリ | 39,424 KB |
最終ジャッジ日時 | 2024-12-20 20:19:29 |
合計ジャッジ時間 | 15,029 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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[l-j-1];}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[l-k-1]);}}}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[l-i-1];}for(ll i=0;i<n;i++){if(num==seg[i].prod(0,(ll)t.size())){ans++;}}cout<<ans<<endl;}}}