记录编号	610265	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[WC 2016] 论战捆竹竿	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	3.275 s
提交时间	2025-12-19 19:48:55	内存使用	8.87 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll inf=1e18+5;
int T,n,nxt[N],b[N],m,mod,p[N],q[N];
ll w,f[N],ans,g[N];
char s[N];
void clear(){
	for(int i=1;i<=n;i++)f[i]=nxt[i]=0;
	for(int i=1;i<=m;i++)b[i]=0;
	m=ans=mod=0;return;
}
ll gcd(ll n,ll m){
	return m==0?n:gcd(m,n%m);
}
ll val(ll j,ll d){
	return f[p[j]]-j*d;
}
void work(int st,int d,int c){
	int cnt=gcd(st,mod);
	for(int i=0;i<mod;i++)g[i]=f[i],f[i]=inf;
	for(int i=0;i<mod;i++)f[g[i]%st]=min(f[g[i]%st],g[i]);
	int j,t,l,r;
	for(int i=0;i<cnt;i++){
		j=(i+mod)%st;
		for(p[t=1]=i;;(j+=mod)%=st){
			if(j==p[1])break;
			else p[++t]=j;
		}
		for(int j=t+1;j<=(t<<1);j++)p[j]=p[j-t];
		t<<=1;
		for(int j=2;j<=t;j++){
			f[p[j]]=min(f[p[j]],f[p[j-1]]+mod);
		}
	}
	mod=st;
	if(d<0)return;
	cnt=gcd(d,mod);
	for(int i=0;i<cnt;i++){
		j=(i+d)%mod;
		for(p[t=1]=i;;(j+=d)%=mod){
			if(j==p[1])break;
			else p[++t]=j;
		}
		for(int j=t+1;j<=(t<<1);j++)p[j]=p[j-t];
		t<<=1;l=1,r=0;
		for(int j=1;j<=t;j++){
			while(l<=r&&j-q[l]>c)l++;
			if(l<=r)f[p[j]]=min(f[p[j]],1ll*j*d+val(q[l],d)+st);
			while(l<=r&&val(q[r],d)>=val(j,d))r--;
			q[++r]=j;
		}
	}
	return;
}
void work(){
	scanf("%d %lld",&n,&w);
	scanf("%s",s+1);w-=n;
	if(w<0){
		printf("0\n");
		return;
	}
	for(int i=2;i<=n;i++){
		int p=nxt[i-1];
		while(s[p+1]!=s[i]&&p)p=nxt[p];
		if(s[p+1]==s[i])nxt[i]=++p;
	} 
	int l=nxt[n];
	while(l){
		b[++m]=n-l;
		l=nxt[l];
	}
	b[++m]=n;
	for(int i=1;i<=n;i++)f[i]=inf;
	f[0]=0,mod=n;
	for(int i=1,j;i<=m;i=j){
		int diff=b[i+1]-b[i];j=i;
		while(diff==b[j+1]-b[j])j++;
		work(b[i],diff,j-i-1);
	}
	for(int i=0;i<mod;i++){
		if(f[i]<=w)ans+=(w-f[i])/mod+1;
	}
	printf("%lld\n",ans);
	return; 
}
signed main(){
	freopen("jie.in","r",stdin);
	freopen("jie.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		work();
		clear();
	}
	return 0;
}