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

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

一月 02, 2021

题目：

竹林里有无数根完全一样的短竹子,每一根竹子由 n 节组成,每一节都被染上了颜色,竹子不可以颠倒。
每次你可以选择一根短竹子,短竹子底端若干节(可以是 0节)与竹竿的最上面若干节对应地一节一节捆起来,而短竹子前面剩下的节伸出去,这样就得到了一根更长的竹竿。小 W 对竹竿的审美要求很高,他捆竹竿时有一个癖好:如果两根竹子的某两节被捆在了一起,那么它们的颜色必须相同。现在请你求出在竹竿长度超过 w 的情况下,小 W 可以捆出多少种长度不同的竹竿。其中,竹竿的长度指从底端到顶端的
竹子的节的个数。
$n \le 5 \cdot 10^5 ,w \le 10^{18}$。

众所周知 $border$ 有一个性质：

字符串 $S$ 的所有 border 可以被划分成不超过 $\log_2|S|$ 段，每一段的长度是等差数列。

假设现在有 $k$ 个等差数列。

不妨，先考虑其中的一个：$x_1,x_1+d_1,x_1+2d_1,\cdots,x_1+len*d_1$。

考虑求出在 $\bmod x_1$ 意义下的同余最短路。其实可以发现，所有的转移会将序列分为 $\gcd(x_1,d_1)$ 个环。从环上 $dis$ 最小的点开始转移即可。

考虑现在新加入了：$x_2,x_2+d_2,x_2+2d_2,\cdots,x_2+len*d_2$。

那么现在的模数要切换到 $x_2$。可以发现首先有 $dis’_{dis_i \bmod x2}=dis_i$ 但这样转移是会漏情况的，因为还有 $dis_i+k*x_1$ 的转移。这样直接再在 $\bmod x_2$ 意义下跑一遍同余最短路就行了。

之后继续像之前那样考虑 $\bmod x_2$ 意义下的同余最短路即可。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define int long long
il int read()
{
	int k=1,re=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')k=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){re=re*10+ch-48;ch=getchar();}
	return re*k;
}
il void write(int x)
{
	if(x<0)return putchar('-'),write(-x),void();
	if(x<=9)return putchar(x+48),void();
	return write(x/10),write(x%10),void();
}
int n,T,W,nxt[500005],f[500005],las;
char s[500005];
int b[500005],lb;
const int M=998244353;
void getb()
{
	int k=0;
	for(rg int i=2;i<=n;i++)
	{
		while(k&&s[i]!=s[k+1])k=nxt[k];
		nxt[i]=(s[i]==s[k+1])?++k:0;
	}
	while(k)
	{
		b[++lb]=n-k;
		k=nxt[k];
	}
}
int gcd(int u,int v)
{
	if(!v)return u;
	return gcd(v,u%v);
}
int st[1000005],ls,p[500005],Q[500005],lq,w[500005],tl,hd,pos[500005];
void tomod(int x)
{
	int g=gcd(x,las);
	for(rg int i=0;i<las;i++)
		p[i]=f[i];
	for(rg int i=0;i<x;i++)
		f[i]=0x3f3f3f3f3f3f3f3f;
	for(rg int i=0;i<las;i++)
		f[p[i]%x]=min(p[i],f[p[i]%x]);
	for(rg int i=0;i<g;i++)
	{
		ls=0;st[++ls]=i;int now=(i+las)%x;
		while(st[1]!=now)
		{
			st[++ls]=now;
			now=(now+las)%x;
		}
		for(rg int j=1;j<=ls;j++)
		{
			st[ls+j]=st[j];
		}
		ls<<=1;
		for(rg int j=2;j<=ls;j++)
			f[st[j]]=min(f[st[j-1]]+las,f[st[j]]);
	}
	las=x;
}
void sol(int x,int sz,int d)
{
	int g=gcd(x,d);
	tomod(x);
	
	if(d<0)return;
	for(rg int i=0;i<g;i++)
	{
		ls=lq=0;Q[++lq]=i;int now=(i+d)%x,tt=1;
		while(Q[1]!=now)
		{
			if(f[Q[tt]]>f[now])tt=lq+1;
			Q[++lq]=now;now=(now+d)%x;
		}
		for(rg int j=tt;j<=lq;j++)
			st[++ls]=Q[j];
		for(rg int j=1;j<tt;j++)
			st[++ls]=Q[j];
		hd=tl=0;
		w[0]=f[st[1]]-d;pos[0]=1;
		for(rg int j=2;j<=ls;j++)
		{
			while(hd<=tl&&pos[hd]<j-sz)hd++;
			if(hd<=tl)f[st[j]]=min(f[st[j]],w[hd]+j*d+x);
			while(hd<=tl&&w[tl]>f[st[j]]-j*d)tl--;
			w[++tl]=f[st[j]]-j*d;pos[tl]=j;
		}
	}
}
signed main()
{
	T=read();
	while(T--)
	{
		n=read();W=read()-n;
		scanf("%s",s+1);lb=0;
		getb();memset(f,0x3f,sizeof(f));memset(nxt,0,sizeof(nxt));las=n;
		f[0]=0;b[lb+1]=0;
		for(rg int i=1,j=1;i<=lb;i=j)
		{
			while(b[i+1]-b[i]==b[j+1]-b[j])j++;
			sol(b[i],j-i-1,b[i+1]-b[i]);
		}
		int ans=0;
		for(rg int i=0;i<las;i++)
		{
			if(f[i]<=W)
				ans+=(W-f[i])/las+1;
		}
		write(ans);puts("");
	}
}