Original link: https://www.shuizilong.com/house/archives/liberoj-3723-%E3%80%8Csdoi-sxoi2022%E3%80%8D%E5%AD%90%E4%B8%B2%E7% BB%9F%E8%AE%A1/
Title meaning
Very amazing question. . . Consider violent dp. . It is not difficult to have. .
FOR(i, 1, n) {
REP(l, ni) {
int r = l + i;
dp[l][r] = (dp[l+1][r] + dp[l][r-1]) * occ[l][r];
}
}
As long as the suffix array is used to preprocess the occ, the complexity is O(n2).
#include <lastweapon/bitwise>
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(5e3) + 9;
int C[N], key[N], t1[N], t2[N];
int n;
namespace SA {
const int Z = 27;
int a[3*N], sa[3*N], rk[N], h[N];
inline void rs(int*x,int*y,int*sa,int n,int m){
REP(i, n)key[i]=i[y][x];
memset(C, 0, sizeof(C[0])*m);
REP(i, n) ++C[key[i]];
FOR(i, 1, m) C[i] += C[i-1];
DWN(i, n, 0) sa[--C[key[i]]] = y[i];
}
void da(int*a,int*sa,int n,int m){
int *x = t1, *y = t2;
memset(C,0,sizeof(C[0])*m);
REP(i, n)++C[x[i]=a[i]];
FOR(i, 1, m)C[i]+=C[i-1];
DWN(i, n, 0)sa[--C[x[i]]]=i;
for(int l=1,p=1;p<n;l<<=1,m=p){
p=0; FOR(i, nl, n) y[p++]=i;
REP(i, n) if (sa[i]>=l) y[p++]=sa[i]-l;
rs(x,y,sa,n,m),swap(x,y),x[sa[0]]=p=0;FOR(i, 1, n)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l]) ?p:++p;
++p;
}
}
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int*r, int a, int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k, int*r, int a, int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}
void dc3(int*a, int*sa, int n, int m){
int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)/3, tbc=0, p;
a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;
rs(a+2,t1,t2,tbc,m),rs(a+1,t2,t1,tbc,m),rs(a,t1,t2,tbc,m);
p=0,an[F(t2[0])]=0;FOR(i, 1, tbc)
an[F(t2[i])]=c0(a,t2[i-1],t2[i])?p:++p;
if (++p < tbc) dc3(an,san,tbc,p);
else REP(i, tbc) san[an[i]] = i;
REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;
if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);
REP(i, tbc) key[t2[i]=G(san[i])] = i;
for(i=0,j=0,p=0; i<ta && j<tbc; p++)
sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];
for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];
}
void get_h(){
REP_1(i, n) rk[sa[i]] = i;
int k=0;for(int i=0;i<n;h[rk[i++]]=k){
if (k)--k;for(int j=sa[rk[i]-1];a[i+k]==a[j+k];++k);
}
}
void bd(){
dc3(a,sa,n+1,Z),get_h();
}
} using namespace SA;
char s[N]; Int dp[N][N]; int occ[N][N];
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
MOD = 998244353;
n = strlen(RS(s)); REP(i, n) a[i] = s[i] - 'a' + 1; bd();
REP(i, n) {
int l = rk[i], r = l+1;
DWN(j, n, i) {
int len = j-i+1;
while (h[l] >= len) --l;
while (h[r] >= len) ++r;
occ[i][j] = rl;
}
}
REP(i, n) dp[i][i] = occ[i][i];
FOR(i, 1, n) {
REP(l, ni) {
int r = l + i;
dp[l][r] = (dp[l+1][r] + dp[l][r-1]) * occ[l][r];
}
}
cout << dp[0][n-1] << endl;
//Display(occ, n, n);
//Display(dp, n, n);
}
Further we observe the occ array. It is found to be very regular, so divide and conquer FFT can be used. . .
This article is reproduced from: https://www.shuizilong.com/house/archives/liberoj-3723-%E3%80%8Csdoi-sxoi2022%E3%80%8D%E5%AD%90%E4%B8%B2%E7% BB%9F%E8%AE%A1/
This site is only for collection, and the copyright belongs to the original author.