题解 P4156 【[WC2016]论♂战♂捆竹竿】

· · 题解

神仙题 QAQ

先给个定义:

一个字符串的 border : 如果一个正整数 len 对于字符串 S 来说满足 S_{1} \dots S_{len} = S_{|S|-len+1} \dots S_{|S|} 且 len \leq |S|,则称 len 为 S 的一个 border. 如 3 就是 ababa 的一个 border. 显然一个字符串可能有多个 border

在本题中,显然我们可以选择 S 的一个 border len ,把前面串结尾的 len 个字符和这次开头的 len 个字符融合起来,这样整个串的长度就增加了 n-len+1.

那就把题目转化为了一个容量为 w 背包问题, 问能放出多少种总重量不大于 w 的长度.

那么暴力哈希求 border, 裸跑同余 BFS, 就有暴力分了.

啥?你不知道什么是同余 BFS? 可以去看一下洛谷这道题: 跳楼机 再来做这道题qwq

然后就有一个很神仙的结论: 把 border 集合中的所有元素排序, 最少可以被划分成的 等差数列 个数不会超过 \log |S| 个.

证明请看官方题解, 我太菜了,不会证.

划分等差数列的意思嘛,举个栗子: 2,3,5,7,9,13,14 最少可以被分成三个等差数列.

那么现在就只用考虑如何用一个等差数列来转移以及不同等差数列的合并.

假设有一个首项为 x , 公差为 d , 项数为 L 的一个等差数列. 设一个状态 f_i 表示到达在模 x 意义下为 i 的点所需要的最短路程.

因为是在模 x 的意义下,所以我们所有的元素都可以被等价地看成是 0, d,2*d,3*d \dots (L-1)*d . 相当于一次可以跳 d 的倍数次,且一次跳的路程不能超过 (L-1)*d.

那么在模 x 意义下, 能跳 d 的倍数长度, 很自然就会形成 \gcd(x,d) 个环. 每个环相互不影响,所以分开dp. 每个环中最小的元素肯定不再会被更新,所以就从每个环中最小的那个元素开始 dp, 因为每次不能跳超过 d 的 L-1 倍次,所以单调队列一下就好了.

这样我们就做完了每个等差数列的转移. 但是还需要把每次算出来的 f 数组合并起来. 但是每个 f 的剩余系 x 并不一样, 这就涉及到了一个模 pre 意义下的 f 数组如何转变为模 now 意义下的 f.

我们把新的 f 看成 g ,那么我们会有这样一个式子:

g_i=\min_{f_j\%now=i} f_j

为啥? 我们在原来的剩余系 pre 中最少走 f_i 就可以到达 i, 在新的剩余系中, 走的这 f_i 步并没有改变, 但是因为模数变成了 now, 到达的终点不再是 i, 而是 f_i\%now. 所以这个值应该被加到 g_{f_i\%now} 上面去.

但是原来在模 pre 意义下, 长度为 pre 的转移并没有被考虑到,所以我们要对新得到的 g 数组上进行一次长度为 pre 的转移才能得到正确的 g.

别人大佬的博客上并没有讲为啥可以这样转移,以上纯属个人yy,如果有错,欢迎指出qwq

那么这样就在 O(n\log n) 的复杂度内通过了此题

贴上代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define int long long
#define ll long long
#define maxn 1000005
using namespace std;
ll Seed=998244353ll;
ll Ha[maxn],pw[maxn];
char s[maxn];
int n,W,Bo[maxn],f[maxn],pre[maxn],now;
void GetBorder()
{
    Bo[0]=0;
    for(int i=1;i<=n;i++)
        Ha[i]=Ha[i-1]+pw[i]*s[i];
    for(int i=1;i<n;i++)
        if(Ha[i]*pw[n-i]==Ha[n]-Ha[n-i]) Bo[++Bo[0]]=i;
    for(int i=1;i<=Bo[0];i++) Bo[i]=n-Bo[i];
    reverse(Bo+1,Bo+Bo[0]+1);
}
int seq[maxn];
void ChangeMod(int x)
{
    int D=__gcd(x,now),top=0;
    for(int i=0;i<now;i++) pre[i]=f[i];
    for(int i=0;i<x;i++) f[i]=1e18;
    for(int i=0,tmp;i<now;i++)
        tmp=pre[i]%x,f[tmp]=min(f[tmp],pre[i]);
    for(int i=0;i<D;i++)
    {
        top=0,seq[++top]=i;
        int tmp=(i+now)%x;
        while(tmp!=seq[1])
            seq[++top]=tmp,tmp=(tmp+now)%x; 
        for(int j=1;j<=top;j++)
            seq[j+top]=seq[j];
        top<<=1;
        for(int j=2;j<=top;j++)
            f[seq[j]]=min(f[seq[j]],f[seq[j-1]]+now);
    }
    now=x;
}
int dq[maxn],w[maxn];
void Solve(int x0,int d,int len)
{
    int D=__gcd(x0,d),top,l,r,N=0;
    static int Q[maxn];
    ChangeMod(x0);
    if(d<0) return;
    for(int i=0;i<D;i++)
    {
        N=0,top=0,Q[++top]=i;
        int tmp=(i+d)%x0;
        while(tmp!=Q[1])
            Q[++top]=tmp,tmp=(tmp+d)%x0;
        int st=1;
        for(int i=1;i<=top;i++) if(f[Q[i]]<f[Q[st]]) st=i;
        for(int i=st;i<=top;i++) seq[++N]=Q[i];
        for(int i=1;i<st;i++) seq[++N]=Q[i];
        l=1,r=1,dq[1]=1,w[1]=f[seq[1]]-d;
        for(int pt=2;pt<=top;pt++)
        {
            while(l<=r&&dq[l]+len<pt) l++;
            if(l<=r) f[seq[pt]]=min(f[seq[pt]],w[l]+pt*d+x0);
            while(l<=r&&w[r]>=f[seq[pt]]-pt*d) r--;
            w[++r]=f[seq[pt]]-pt*d,dq[r]=pt;
        }
    }
}
int T=0;
signed main()
{
    scanf("%lld",&T),pw[0]=1;
    for(int i=1;i<maxn;i++) pw[i]=pw[i-1]*Seed;
    while(T--)
    {
        memset(Bo,0,sizeof(Bo));
        scanf("%lld%lld%s",&n,&W,s+1),W-=n;
        GetBorder(),now=n;
        for(int i=1;i<now;i++) f[i]=1e18; f[0]=0;
        for(int i=1,j=1;i<=Bo[0];i=j)
        {
            while(Bo[i+1]-Bo[i]==Bo[j+1]-Bo[j]) j++;
            Solve(Bo[i],Bo[i+1]-Bo[i],j-i-1);
        }
        int ans=0;
        for(int i=0;i<now;i++)
            if(W-f[i]>=0) ans+=(W-f[i])/now+1;
        printf("%lld\n",ans);
    }
    return 0;
}