結果
問題 |
No.2172 SEARCH in the Text Editor
|
ユーザー |
👑 ![]() |
提出日時 | 2022-12-24 02:02:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,342 bytes |
コンパイル時間 | 1,882 ms |
コンパイル使用メモリ | 107,156 KB |
最終ジャッジ日時 | 2025-02-09 19:53:57 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 WA * 15 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <atcoder/string> #include <atcoder/modint> using namespace std; #define rep(i,n) for(int i=0; i<(int)(n); i++) using Modint = atcoder::static_modint<998244353>; const int SZ = 50; const int SZZ = SZ * (SZ+1) / 2; int Z(const string& preof, const string& sufof){ int x = min(preof.size(), sufof.size()); auto z = atcoder::z_algorithm(preof.substr(0, x) + sufof.substr(sufof.size() - x)); for(int i=x; i>=1; i--) if(z[z.size()-i] >= i) return i; return 0; } string T; int t; int T6L[SZ+1]={}, T6R[SZ+1]={}; int T5[SZ+1][SZ+1]={}; string TPRE[SZ+1]; string TSUF[SZ+1]; vector<string> substrs; int T4[SZZ][SZZ]={}; int T3L[SZZ]={}, T3R[SZZ]={}; int T2L[SZZ][SZ]={}, T2R[SZZ][SZ]={}; int T1[SZ][SZ]={}; void precalc(){ t = T.size(); rep(i,t+1) TPRE[i] = T.substr(0, i); rep(i,t+1) TSUF[i] = T.substr(t-i); rep(i,t+1) T6L[i] = i ? Z(TSUF[i].substr(0,i-1), T) : 0; rep(i,t+1) T6R[i] = i ? Z(T, TPRE[i].substr(1)) : 0; auto sa = atcoder::suffix_array(T); auto lcp = atcoder::lcp_array(T, sa); rep(i,t+1) rep(j,t+1) T5[i][j] = -1; rep(i,t){ int k = i ? lcp[i-1] : 0; for(int j=1; j<=t-sa[i] && j<t; j++){ if(j <= k){ T5[sa[i]][j] = T5[sa[i-1]][j]; continue; } T5[sa[i]][j] = substrs.size(); substrs.push_back(T.substr(sa[i],j)); } } int nn = substrs.size(); rep(i,nn) rep(j,nn) T4[i][j] = -1; rep(k,t+1) rep(j,k) rep(i,j) T4[T5[i][j-i]][T5[j][k-j]] = T5[i][k-i]; rep(j,nn) T3L[j] = Z(substrs[j], T); rep(j,nn) T3R[j] = Z(T, substrs[j]); rep(j,nn) rep(x,t) T2L[j][x] = Z(substrs[j] + TSUF[x], TSUF[t-1]); rep(j,nn) rep(x,t) T2R[j][x] = Z(TPRE[t-1], TPRE[x] + substrs[j]); for(int i=1; i<t; i++) T1[i][t-i] = 1; for(int d=t+1; d<2*t; d++) for(int i=d-t+1; i<t; i++) T1[i][d-i] = T1[T6R[i]][d-i] + T1[i][T6L[d-i]] - T1[T6R[i]][T6L[d-i]]; } struct Node{ int l; int r; Modint c; }; Node createNode(const string& s){ if(s.size() < T.size()){ auto x = lower_bound(substrs.begin(), substrs.end(), s); if(x != substrs.end() && *x == s) return Node{ (int)(x-substrs.begin()), -1, Modint() }; return Node{ Z(s,TSUF[t-1]), Z(TPRE[t-1],s), Modint() }; } int cnt = 0; auto z = atcoder::z_algorithm(T + s); rep(i,s.size()) if(z[t+i]>=t) cnt++; return Node{ Z(s,TSUF[t-1]), Z(TPRE[t-1],s), Modint::raw(cnt) }; } Node mergeNode(Node l, Node r){ if(l.r >= 0){ if(r.r >= 0) return { l.l, r.r, l.c + r.c + Modint::raw(T1[l.r][r.l]) }; return { l.l, T2R[r.l][l.r], l.c + Modint::raw(T1[l.r][T3L[r.l]]) }; } if(r.r < 0){ int nx = T4[l.l][r.l]; if(nx >= 0) return { nx, -1, Modint() }; int lr = T3R[l.r], rl = T3L[r.l]; return { T2L[l.l][rl], T2R[r.l][lr], Modint::raw(T1[lr][rl]) }; } return { T2L[l.l][r.l], r.r, r.c + Modint::raw(T1[T3R[l.l]][r.l]) }; } int main() { int N; cin >> N; cin >> T; precalc(); vector<Node> X(N); rep(i,N){ string s; cin >> s; if(s == "~"){ int j,k; cin >> j >> k; X[i] = mergeNode(X[j-1], X[k-1]); } else{ X[i] = createNode(s); } } cout << X[N-1].c.val() << '\n'; return 0; }