自动搬运

查看原文

来自洛谷，原作者为

	RainWetPeopleStart IX

搬运于2025-08-24 23:06:09，当前版本为作者最后更新于2024-11-18 10:10:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

赛时 70pts 没调完，最后只写了 50pts。

下文中 $T_{[a,a-1]}$ 表示空串（其中 $T$ 是字符串，$a\le|T|$）。

这里稍微改一下前缀的定义（为方便叙述）：

字符串 $R'$ 是字符串 $R$ 的前缀当且仅当存在 $\color{red}{0\le p\le|R|}$ 且 $p$ 为整数使得 $R'=R_{[1,p]}$。

15pts

首先，发现三元组的个数是 $O(|T|^2K)$ 的，考虑暴力枚举三元组，但此时不好 chk。

那如何 chk 呢。考虑 DP，设 $f_{l,r,k}$ 表示 $(l,r,k)$ 是否合法，转移时枚举新加的串的位置即可，复杂度 $O(n^4)$。（不过这个东西貌似可以bitset优化，可能能过 30）

30pts

发现一个状态表示一个 bool 十分浪费，考虑优化。发现若 $f_{l,r,k}$ 合法，则可以通过添加空串的方式使 $f_{l,r,k+1}$ 合法，可以设 $f_{l,r}$ 表示使 $(l,r,k)$ 合法的最小 $k$ 值，就有转移 $f_{l,r}=\min_{l<i\le r+1}(f_{i,r})+1$（要求 $T_{[l,i-1]}$是某个 $S_i$ 的前缀）。

判断前缀可以使用哈希，复杂度 $O(n|T|^3)$，用 trie 则为 $O(|T|^3)$。（实际上加剪枝后在原题数据中可以拿 50pts）

50pts

考虑优化转移，上文中合法的 $i$ 构成了一段区间，此时可以预处理出 $to_i$ 表示最大的 $j$ 使 $T_{[i,j]}$ 是某个 $S_i$ 的前缀（因为 $T_{[i,i-1]}$ 是空串，故 $j$ 一定存在）。

此时 $i$ 的上界为 $\min(to_l,r)+1$。由于对查 $f_{i,r}$ 而言，左端点是递减的，可以使用单调栈上二分，复杂度 $O(|T|^2\log|T|)$。

70pts

此时状态数会炸，考虑将状态与 $K$ 挂钩。

发现对于 $l,k$ 来说，使 $(l,r,k)$ 合法的 $r$ 构成一段区间，考虑交换状态和答案，记 $f_{l,k}$ 表示使 $(l,r,k)$ 合法的最大的 $r$。

转移如下：

$f_{l,k}=\max_{l\le i\le f_{l,k-1}+1}(f_{i,1})$。

其中 $f_{i,1}=to_i$。方便起见，可设 $f_{|T|+1,1}=|T|$。

转移就相当于 RMQ，可以 ST 表维护。

如何求 $to_i$ 呢，注意到 $to_i$ 具有可二分性，使用字符串哈希 chk 即可。

答案为 $\sum\limits_{i=1}^{|T|}\sum\limits_{j=1}^Kf_{i,j}+1-i$。

下面考虑第二问，每一个 $f$ 值对答案的贡献形如区间加等差数列，将其变为在二重差分数组上单点改，最后还原即可。

复杂度 $O(K|T|+n|T|\log|T|)$。

100pts

发现 max 里面 $k$ 那一维是 1，能不能依此优化？

可以的，记 $tr_{i,j}$ 表示区间 $[i,j]$ 中使 $to_i$ 取最大值的 $i$。可以将转移过程大致抽象为：

1.对当前区间求 $tr$。

2.更新 $r$ 为 $to_{tr}$ 并转移到 $k+1$。

此时，我们发现，$[l,tr-1]$ 的 $to$ 值一定不会成为 max。

修改 $tr$ 定义，设 $tr_i$ 表示 $[i,to_i+1]$ 中使 $to_i$ 取最大值的 $i$。

依此建 $tr_i\rightarrow i$ 的边，发现建出来的是根节点为自环的外向“森林”，转移到 $k+1$ 就相当于跳父亲（定义根节点父亲为自身）。

设当前在点 $u$，则所对 $f$ 值为 $to_u$。

我们求出 $s_u$ 表示 $\sum\limits_{i=1}^Kf_{u,i}$。$v_u$ 表示有多少个 $f$ 值跳到了 $u$，前者可以树上倍增，后者可以树上差分求，可以依据这两个东西来做第二问，依据 $s$ 做第一问。

综上，本题在 $O(n|T|\log|T|)$ 的时间复杂度内得到解决。

代码

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
const int N1=5050,N=5e5+10,SG=30;
int n,K;int sub;
int to[N];
int hs[12][N],ln[12],pb[N];
int base=131,mod=1011451423;
int hsh[N];
int gh(int l,int r){
    return (hsh[r]-1ll*pb[r-l+1]*hsh[l-1]%mod+mod)%mod;
}ll g[N];
int tr[N];
struct segtree{
    pii T[N<<2];
    #define ls p*2
    #define rs p*2+1
    #define mid (l+r)/2
    void pu(int p){
        T[p]=max(T[ls],T[rs]);
    }
    void bd(int p,int l,int r){
        if(l==r){
            T[p]=mk(to[l],-l);return ;
        }bd(ls,l,mid);bd(rs,mid+1,r);pu(p);
    }pii qry(int p,int l,int r,int pl,int pr){
        if(pl<=l&&r<=pr) return T[p];
        pii res=mk(-1,0);
        if(pl<=mid) res=max(res,qry(ls,l,mid,pl,pr));
        if(pr>mid) res=max(res,qry(rs,mid+1,r,pl,pr));
        return res;
    }
    #undef ls
    #undef rs
    #undef mid
}sgt;
vector<int> E[N];
int dep[N];
int fa[N][22];ll sm[N][22];
bool vis[N];
ll val[N],sum[N],tg[N];
void dfs(int u,int pr){
    vis[u]=1;dep[u]=dep[pr]+1;
    fa[u][0]=pr;sm[u][0]=to[u];
    for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1],sm[u][i]=sm[u][i-1]+sm[fa[u][i-1]][i-1];
    for(auto v:E[u]) if(!vis[v]) dfs(v,u);
}void dfs2(int u){
    vis[u]=1;
    for(auto v:E[u]){
        if(!vis[v]) dfs2(v),val[u]+=val[v];
    }
}
void slv1(){
    cin>>n>>K;
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        ln[i]=s.length();
        int hsh=0;
        for(int j=0;j<ln[i];j++){
            hsh=1ll*hsh*base%mod;
            hsh=(hsh+s[j]-'a')%mod;
            hs[i][j+1]=hsh;
        }
    }string t;cin>>t;
    int len=t.length();
    t=' '+t;
    for(int i=1;i<=len;i++){
        hsh[i]=1ll*hsh[i-1]*base%mod+t[i]-'a';
        hsh[i]%=mod;
    }pb[0]=1;for(int i=1;i<=len;i++) pb[i]=1ll*pb[i-1]*base%mod;
    for(int i=1;i<=len;i++){
        int l=i-1,r=len;
        while(l<r){
            int mid=(l+r+1)/2;
            int hsh1=gh(i,mid),lenn=mid-i+1,cnt=0;
            for(int j=1;j<=n;j++){
                if(lenn>ln[j]) continue;
                if(hsh1==hs[j][lenn]) cnt++;
            }
            if(cnt>0) l=mid;
            else r=mid-1;
        }to[i]=l;
    }to[len+1]=len;
    sgt.bd(1,1,len+1);
    for(int i=1;i<=len;i++) tr[i]=-sgt.qry(1,1,len+1,i,to[i]+1).se;
    for(int i=1;i<=len;i++) E[tr[i]].push_back(i);
    for(int i=len;i>=1;i--) if(!vis[i]) dfs(i,i);
    ll ans=0;
    for(int i=1;i<=len;i++){
        ll s=0;int now=i;
        for(int j=19;j>=0;j--){
            if((K>>j)&1) s+=sm[now][j],now=fa[now][j];
        }ans+=s;sum[i]=s;
        if(dep[i]>K){
            val[i]++,val[now]--;
        }else{
            val[i]++,val[now]--;tg[now]+=K-(dep[i]-1);
        }vis[i]=0;sum[i]+=K;sum[i]-=1ll*K*i;
        //cout<<i<<' '<<now<<endl;
    }
    ans+=1ll*len*K;ans-=1ll*K*(1ll*len*(len+1)/2);
    for(int i=len;i>=1;i--) if(!vis[i]) dfs2(i);
    for(int i=1;i<=len;i++){
        val[i]+=tg[i];//cout<<i<<' '<<val[i]<<' '<<dep[i]<<endl;
        g[i+1]-=K;g[i]+=sum[i];g[i+1]-=sum[i];g[to[i]+2]+=val[i];
    }
    for(int i=1;i<=len;i++) g[i]+=g[i-1];
    for(int i=1;i<=len;i++) g[i]+=g[i-1];
    cout<<ans<<endl;for(int i=1;i<=len;i++) cout<<g[i]<<' ';
}
int main(){
    cin>>sub;
    slv1();
    return 0;
}