P11291 解题报告

前言

感觉很神的题。

个人感觉比简单的字符串问题要 hard 很多。

思路分析

第一问

9 分做法

优先考虑下第一问先。

我们显然的有一个暴力的做法，直接进行一个区间 dp。

转移就是设两个好的三元组 (l,i,k_1),(i,r,k_2)，那么三元组 (l,r,k_1+k_2) 就是好的。

这个复杂度是 O(K|T|^3)，期望得分 9，代码笔者没写（）。

18 分做法

然后我们来考虑优化。

类似于简单的字符串问题中的 R 字符串可空的定义，我们可以观察到一个单调性。

那么就是 (l,r,k),k<K 若为好的，(l,r,k+1) 也一定是好的。

原因很简单，你直接多插入一个空的字符串在末尾就行了。

我们现在的问题就变成了计算对于每个 (l,r)，求最小的 k 满足 (l,r,k) 是好的。

那么我们就可以想到枚举 (l,r) 去计算。

把一个串拆分为最小段数的前缀，其中前缀让我们想到了 trie。

所以我们只要把 (l,r) 这段字符串扔到 trie 上尝试贪心的拆分就行了。

具体的，我们尝试把这段字符串 s 拆分为 t'+t，其中 t' 是一段前缀，可以通过在 trie 上走求出来，而拆分 t 的方法直接通过前面已经求的值转移就行了。

那这样的话我们先枚举长度 i，再枚举左端点 l，得出右端点 l+i-1 就可以转移了。

复杂度 O(|T|^3)，期望得分 18，实际得分 30，代码可以见 link。

30 分做法

上面的代码理论而言不能拿到 30 分，所以我们可以进一步优化复杂度。

其实这里就是一个平衡复杂度的过程。

每次都在 trie 上跳一遍太浪费时间了，我们不妨直接预处理出来每个点开始能最多跳几步，这样就是一个 O(|T|^2) 的预处理。

然后查询就变成了一个树链的 \min，可以用线段树来实现。

复杂度 O(|T|^2\log|T|)，期望得分 30，实际得分 30，code by sgl654321。

30 分做法

然后这个做法貌似就没什么优化的余地了没前途的做法，我们考虑进一步观察性质。

其实我们可以发现这里还有一个单调性。

就是如果 (l,r,k) 不是好的，那么 (l,r+1,k) 也一定不是好的。

略证一下，既然 (l,r) 不能用 k 个前缀拼出，那么 (l,r+1) 不妨拆分为 (l,r) 和 (r,r)。

拆分出的两者中前者都不能用 k 个前缀拼出，加起来显然也不行了。

有了这个单调性我们就有了另一种 dp 的定义方式。

这次我们不钦定 l,r 计算 k，而是选择钦定 l,k，计算可能的最大 r。

由前面的性质，我们知道可能的 r 是一段连续的区间，而左端点就是 l，所以记录一个最右端点即可。

设这个定义的最右端点为 g_{l,k}，那么我们可以先预处理出 g_{l,1}。

这东西就是 l 出发最多能匹配上的长度，在 trie 树上暴力跑一遍就可以做到 O(|T|^2)。

然后我们考虑暴力的转移，对于 g_{l,k} 而言：

g_{l,k}\leftarrow\max\limits_{i=l}^{g_{l,k-1}+1}g_{i,1}

考虑下这个式子的意义。

就是对于 i\in[l,g_{l,k-1}+1]，我们可以用 k-1 个前缀把 [l,i) 拼出来，最后再尝试一个前缀从 i 处开始匹配最远能匹配到的位置转移即可。

这个东西有关的值只有 g_{i,1},i\in[1,|T|]，所以我们可以把这些值全部扔到 ST 表里去，每次就是一个区间查询。

那么总的复杂度就是 O(|T|^2+|T|\log|T|+K|T|)，期望得分 30，代码笔者懒得写（）。

当然如果你用四毛子就可以把丑陋的 \log 剥掉。

42 分做法

然后继续优化这个东西。

发现复杂度瓶颈在 trie 的这个预处理上，我们考虑加速这个预处理。

这个预处理其实就是在找从位置 i 开始，尝试对每种串的前缀进行匹配，找到一个最长的匹配。

这种匹配我们可以用 hash+二分的经典技巧来加速，可以做到 O((n|S|+|T|)\log |S|)。

这样的总复杂度就来到了 O((n|S|+|T|)\log |S|+|T|\log|T|+K|T|)，期望得分 30，实际得分 30。

当然你也可以用 Z 函数直接剥掉 hash+二分的 \log。

code by Hoks。

当然你还可以通过数据点分治的方法拿到 11\sim14 的分，期望得分 42。

60 分做法

然后我们来考虑最后一个优化。

前面不管我们怎么优化，都会有一个无法逾越的瓶颈：

• 我们的 g_{l,k} 的总状态数就是 O(K|T|) 的，对每个求值复杂度不可能低于 O(K|T|)。

其实我们可以注意到的是，对于这 O(K|T|) 个状态，总共只有 O(|T|) 种取值。

因为所有的 g_{1,k},k>1 的值都是从某个 g_{x,1} 取来的，所以取值只有 O(|T|) 种。

考虑观察这些取值之间互相转移的性质。

不妨设 f_{l,k} 表示 g_{l,k}=g_{f_{l,k},1}。

因为 g_{l,k}=\max\limits_{i=l}^{g_{l,k-1}+1}g_{i,1}=g_{f_{l,k},1}。

所以 f_{l,k} 一定不劣于 i\in[l,f_{l,k}]，可以直接把这段无用区间去掉。

那么我们考虑 g_{l,k+1}=\max\limits_{i=l}^{g_{l,k}+1}g_{i,1}=\max\limits_{i=f_{l,k}}^{g_{f_{l,k},1}+1}g_{i,1}。

换元法，我们令 l'=f_{l,k}，那么最右边的那个式子就可以化为 \max\limits_{i=l'}^{g_{l',1}+1}g_{i,1}=g_{l',2}=g_{f_{l',2},1}。

然后我们就得到了 f_{l,k+1}=f_{l',2}=f_{f_{l,k},2}。

这东西长得一脸图的样子，我们直接建图，给 i\rightarrow f_{i,2} 连边，那么 i 跳 k 步到达的 k 级祖先即为 f_{i,k+1}。

那么我们就可以把第一问的答案用一个形式化的式子表达出来：

\sum\limits_{i=1}^{|T|}\sum\limits_{j=1}^K(g_{f_{i,j},1}-i+1)

把中间平凡的 -i+1 剥出来再化简可以得到：

\sum\limits_{i=1}^{|T|}\sum\limits_{j=1}^Kg_{f_{i,j},1}-K\sum\limits_{i=1}^{|T|}i+K|T|

后两项是平凡的，只需要考虑第一项就可以了。

因为 g_{l,1} 的取值只有 |T| 种，所以我们只要对每种 l 数有多少 f_{i,j}=1 就行了。

那么就是对于每个 i 来讲对他的 j 级祖先出现次数 +1，这东西可以简单树上差分然后前缀和解决。

但是注意树的根节点有自环，要特殊处理。

使用 Z 函数，这样我们就在 O(n(|T|+|S|)+|T|\log|T|) 的复杂度完成了第一问，期望得分 60。

当然如果会四毛子+长剖可以去掉 \log|T|。

当然这个东西他求的 k 级祖先是固定的，直接记录的方法就可以省掉大常的长剖了。

code by Hoks。

实际得分 60，但是调的我很折磨，从 57\rightarrow54\rightarrow21\rightarrow60，前面两个甚至对拍都拍不出来。

第二问

15 分做法

做完第一问后，我们来考虑第二问。

首先是对于最开头写的 O(K|T|^3) 的暴力。

在算出 (l,r,k) 为好的后暴力枚举 i\in[l,r] 给当前位置值 +1 就行了。

复杂度还是 O(K|T|^3)，期望得分 15。

30/50 分做法

接着是 O(|T|^3) 和 O(|T|^2\log |T|) 的做法。

因为其本质并没有区别，所以第二问的做法相同。

我们现在已经处理出了 (l,r) 的最小值 k，那么 i\in[k,K],(l,r,i) 都是好的。

也就是对于 [l,r] 一个区间加 K-k+1，暴力做是 O(|T|^3)，随便扔个 DS 是 O(|T|^2\log|T|)，差分前缀和是 O(|T|^2)。

第一个期望得分 30，剩下的两个结合 O(|T|^3) 期望得分 30，结合 O(|T|^2\log |T|) 期望得分 50。

实际而言得分都是 50。

代码可以看上面附的链接。

50/70 分做法

然后是对于有前途钦定了 l,k 做法的第二问。

第一种是无脑的做法，我们直接通过 g 求出 f 然后就变成了和上面一样的东西。

这样期望得分 50，实际得分 50。

code by Hoks。

但这样还是没有前途太劣了。

我们不妨直接对每个 g_{l,k} 去考虑他的贡献。

他的贡献就是对于区间 i\in[l,g_{l,k}] 加上 g_{l,k}-i+1。

这里面有一个 i 看着非常 ex，所以我们先通过一次差分前缀和的方法给每个位置 -1，做到把式子转化为 g_{l,k}-l+1。

然后再差分一次前缀和累加就行了。

具体的先给 l+1 位置减 1，g_{l,k}+2 位置加 1。

然后前缀和累加一次。

再给 l 位置加 g_{l,k}-l+1，再前缀和累加一次就可以得到正确的答案了。

复杂度和前面的期望 42 分的做法一样，这样期望得分来到 70，实际得分也是 70。

code by Hoks，非常丑陋就是给一个东西拼了两次（）。

100 分做法

然后我们考虑 100 pts 做法。

根据前面的 60 pts 第一问做法，我们知道求的这个值其实就是一个森林上跳 k 步的问题。

我们尝试把刚刚的 70 pts 做法推广到森林上来。

修改之后我们的具体操作就是：

1. 给 l+1 位置 -K。
2. 给 g_{l,1}+2 位置加上 g_{l,1} 的统计次数。
3. 然后累加一遍前缀和。
4. 给 l 位置加上 \sum\limits_{k=0}^{K-1}g_{l,k}-K\cdot(i-1)。
5. 再累加一遍前缀和。

这其实就只是把刚刚的操作扔到森林上来了。

细节注意点还是相同的，注意根节点的自环。

实现上而言，我们可以不用真的这样二阶前缀和，直接二阶差分把值差分出来就行了。

复杂度仍是 O(n(|T|+|S|)+|T|\log|T|) 期望得分 100，实际得分 100。

代码

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=1e6+10,V=315,M=23,INF=1e9,mod=998244353;
int n,m,k,ans,l[N],z[N<<1],g[N];char s[M][N],t[N],ss[N<<1];
vector<int>e[N];int top,st[N],f[N],kf[N],mp[N],a[N],b[N],c[N],d[N];
int tt[M][N],stt[M][N];
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void flush(){fwrite(out,1,length,stdout);length=0;}
    inline void put(char c){if(length==9999999) flush();out[length++]=c;}
    inline void put(string s){for(char c:s) put(c);}
    inline void print(int x)
    {
        if(x<0) put('-'),x=-x;
        if(x>9) print(x/10);
        put(x%10+'0');
    }
    inline bool chk(char c) { return !(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'||c=='|'||c=='-'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
namespace function_Z
{
    inline void get_Z(char s[],int n,int z[])
    {
        for(int i=2,l=1,r=0;i<=n;i++)
        {
            z[i]=i>r?0:min(z[i-l+1],r-i+1);
            while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]) z[i]++;
            if(i+z[i]-1>r) l=i,r=i+z[i]-1;
        }z[1]=n;
    }
}
using namespace function_Z;
inline void dfs1(int u,int rt)
{
    st[++top]=u;d[u]=d[f[u]]+1;b[u]=b[f[u]]+g[u];
    if(top>=k) kf[u]=st[top-k+1];
    else{kf[u]=rt;if(mp[u]) ans+=(k-top)*g[rt];}
    for(int v:e[u]) dfs1(v,rt);a[f[kf[u]]]--,a[u]++;top--;
}
inline void dfs2(int u,int t)
{
    for(int v:e[u]) dfs2(v,t),a[u]+=a[v];ans+=a[u]*g[u];int cur=0;
    if(d[u]>=k) cur=b[u]-b[f[kf[u]]]-k*(u-1);
    else cur=(k-d[u])*g[t]+b[u]-k*(u-1),c[g[t]+2]+=k-d[u];
    c[u]+=cur,c[u+1]-=cur+k,c[g[u]+2]+=a[u];
}
inline void solve()
{
    n=read();k=read();for(int i=1;i<=n;i++) rd(s[i],l[i]);rd(t,m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) if(s[i][1]==t[j]) mp[j]=1;
        for(int j=1;j<=l[i];j++) ss[j]=s[i][j];
        for(int j=1;j<=m;j++) ss[j+l[i]]=t[j];get_Z(ss,m+l[i],z);
        for(int j=1;j<=m;j++) g[j]=max(g[j],j+min(l[i],z[j+l[i]])-1);
    }for(int j=1;j<=m;j++) if(mp[j]) stt[0][j]=g[j],tt[0][j]=j;
    for(int j=1;j<M;j++)
        for(int i=1;i+(1<<j)-1<=m;i++)
        {
            if(stt[j-1][i]>stt[j-1][i+(1<<j-1)]) tt[j][i]=tt[j-1][i];
            else tt[j][i]=tt[j-1][i+(1<<j-1)];
            stt[j][i]=max(stt[j-1][i],stt[j-1][i+(1<<j-1)]);
        }
    for(int i=1;i<=m;i++)
    {
        if(!mp[i]){f[i]=i;continue;}int r=g[i]+1,K=log2(r-i+1);
        if(stt[K][i]>stt[K][r-(1<<K)+1]) f[i]=tt[K][i];
        else f[i]=tt[K][r-(1<<K)+1];
        if(f[i]!=i) e[f[i]].emplace_back(i);else f[i]=0;
    }for(int i=1;i<=m;i++) if(!f[i]) dfs1(i,i),dfs2(i,i);
    for(int i=1;i<=m;i++) if(mp[i]) ans-=(i-1)*k;
    print(ans);put('\n');
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=1;i<=m;i++) print(c[i]),put(' ');
}
signed main()
{
    int T=1,tp=read();
    // T=read();
    while(T--) solve();
    genshin:;flush();return 0;
}