题目链接：https://www.luogu.com.cn/problem/P4156

题目大意：每一开始你有一个字符串 $s$ ，然后你可以在字符串末尾加入 $s$ 并删除末尾一个 $s$ 的 Border ，问你最终能得到多少个不超过 $w$ 的不同长度。

做法

首先，如何计数？观察到我们只要知道对于 $\forall k\in \{0,1,…,n-1\}$ ，最小的长度 $len_k$ 满足：$len_k\equiv k\mod{n}$ 。

这样就能够在 $O(n)$ 的时间内计算答案了。

这时一个很暴力的想法是求出所有的 Border 然后做同余最短路，时间复杂度 $O(n^2)$ 。

这个时候就要利用 Border 的性质做一些优化了，Border 有一个性质：能够把所有 Border 划分成恰好 $\log$ 段等差数列。

不妨将长度设为 $l,l+d,l+2d,…,l+(s-1)d$ 。

这时候还要观察到一个事情：如果把这个问题想象成背包，这个背包的体积和价值是一样的，这能够产生一个什么性质呢？不妨认为 $len_k\equiv t\mod{l}$ ，我们只要先在$\mod{l}$ 意义下跑出最小的 $len’_t$ ，然后再用 $len’_t$ 去更新 $len_k$ 即可。

前一部分可以用单调队列，后一部分连单调队列都不用。

时间复杂度：$O(Tn\log{n})$ 。

空间复杂度：$O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=5e5+5;
const int NN=1e6+5;
const LL inf=1e18+1;
int gcd(int x,int y){return !x?y:gcd(y%x,x);}
int fail[N],n;LL m,dp[N],tmp[N];
char st[N];
PII lis[NN];
int head,tail;
void solve(int l,int s,int d){
    for(int i=0;i<l;i++)tmp[i]=inf+1;
    for(int i=0;i<n;i++)tmp[dp[i]%l]=min(tmp[dp[i]%l],dp[i]);
    int g=gcd(l,d);
    for(int i=0;i<g;i++){
        head=1;tail=0;
        int now=i;
        for(int lim=l/g*2,ti=0;lim;lim--,ti++){
            while(head<=tail && ti-lis[head].second+1>s)head++;
            if(head<=tail)tmp[now]=min(tmp[now],tmp[lis[head].first]+1ll*(ti-lis[head].second)*d+l);
            while(head<=tail && tmp[lis[tail].first]+(ti-lis[tail].second)*d>tmp[now])tail--;
            lis[++tail]={now,ti};
            now=(now+d)%l;
        }
    }
    for(int i=0;i<l;i++){
        dp[tmp[i]%n]=min(dp[tmp[i]%n],tmp[i]);
    }
    g=gcd(l,n);
    for(int i=0;i<g;i++){
        int now=i;LL mi=inf;
        for(int lim=n/g*2;lim;lim--){
            dp[now]=min(dp[now],mi);
            mi=min(mi,dp[now])+l;
            now=(now+l)%n;
        }
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%lld",&n,&m);
        scanf("%s",st+1);
        if(m<n){
            printf("0\n");
            continue;
        }
        m-=n;
        fail[0]=-1;
        int now=0;
        for(int i=2;i<=n;i++){
            while(now!=-1 && st[now+1]!=st[i])now=fail[now];
            fail[i]=++now;
        }
        for(int i=0;i<n;i++)dp[i]=inf+1;
        dp[0]=0;
        now=fail[n];
        while(now){
            int nex=fail[now];
            if(nex+nex<now)solve(n-now,1,1),now=nex;
            else{
                int p=now-nex;
                int l=now%p+p;
                solve(n-now,(now-l)/p+1,p);
                now=l;
            }
        }
        LL ans=0;
        for(int i=0;i<n;i++){
            if(dp[i]<=m)ans+=(m-dp[i])/n+1;
        }
        printf("%lld\n",ans);
    }
    
    
    return 0;
}

我没做出来，我的评价是：菜就多练。

训，狠狠地训。