题解 P9873 [EC Final 2021] Beautiful String

meyi · 2023-11-23 14:53:37 · 题解

2023/11/30 upd: 感谢 zyc212303 指出一处 typo。

貌似写了个常数比较小的做法，目前洛谷最优解 rk1 390ms，比 rk2 825ms 快了一倍。

首先由 s_2=s_5, s_3=s_6 可知 s_2+s_3=s_5+s_6，不妨将它们合并起来看，那么题意就转化为了：定义字符串 t 是美丽的当且仅当将可以 t 视作 t_1+t_2+t_3+t_4，满足 t_1,t_2,t_3,t_4 均非空，且 t_1 为 t_2 的真前缀，t_2=t_4，给定字符串 s，求其有多少子串是美丽的。

考虑 O(n^2) 求 \text{lcp} 的过程，若 i 和 j 的 \text{lcp} 为 k，那么可以将 t_2 视作 s_{i..i+l-1}，将 t_4 视作 s_{j,j+l-1}，(1\le l\le k)，由于 t_3 的存在，因此还需要满足 l< j-i。故我们可以预处理 sum_{i,l} 表示以 i 开头长度为 >l 的选择 t_2 和 t_4 的方案数，那么每个 j 给 sum_i 的贡献是一个等差数列的形式，使用两个前缀和数组处理即可。最后注意到这里的 t_2 是唯一确定的，因此不会重复计数。

然后考虑 t_1 怎么枚举，仍然是在求 \text{lcp} 的过程中，设 i 和 j 的 \text{lcp} 为 k，若 i+k\ge j，则说明 s_{i,j-1} 可以成为 t_1，答案只需累加 sum_{j,j-i} 即可。

时间复杂度 O(n^2)。

代码：

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#define ALL(v) v.begin(),v.end()
#define For(i,_) for(int i=0,i##end=_;i<i##end;++i) // [0,_)
#define FOR(i,_,__) for(int i=_,i##end=__;i<i##end;++i) // [_,__)
#define Rep(i,_) for(int i=(_)-1;i>=0;--i) // [0,_)
#define REP(i,_,__) for(int i=(__)-1,i##end=_;i>=i##end;--i) // [_,__)
typedef long long ll;
typedef unsigned long long ull;
#define V vector
#define pb push_back
#define pf push_front
#define qb pop_back
#define qf pop_front
#define eb emplace_back
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
#define fi first
#define se second
const int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}},inf=0x3f3f3f3f,mod=1e9+7;
const ll infl=0x3f3f3f3f3f3f3f3fll;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
int init=[](){return cin.tie(nullptr)->sync_with_stdio(false),0;}();
int main(){
    int t_case=1;
    cin>>t_case;
    while(t_case--){
        string s;
        cin>>s;
        ll ans=0;
        int n=s.size();
        V<int>lcp(n);
        V<V<int>>sum(n);
        Rep(i,n){
            sum[i].resize(n-i-1>>1);
            V<int>sum2(sum.size());
            FOR(j,i+1,n){
                if(s[i]==s[j]){
                    lcp[j]=(j+1<n?lcp[j+1]:0)+1;
                    if(i+lcp[j]>=j&&j-i<sum[j].size())ans+=sum[j][j-i];
                    if(sum[i].size()){
                        int ed=min(j-i-1,lcp[j]);
                        sum[i][0]+=ed,--sum2[0];
                        if(ed<sum[i].size())++sum2[ed];
                    }
                }
                else lcp[j]=0;
            }
            FOR(j,1,sum[i].size())sum[i][j]+=sum[i][j-1]+sum2[j-1],sum2[j]+=sum2[j-1];
        }
        printf("%lld\n",ans);
    }
    return 0;
}