第二次在bzoj跑进前十竟然是因为在UOJ卡常致死
首先这个题其实就是一个无限背包
一般做法是同余最短路，就是bzoj2118: 墨墨的等式可以拿到30分的好成绩
背包是个卷积就分治FFT优化那么下面20也没问题了 官方做法是大力bitset优化背包并且嘲讽了一波这个做法
再往后需要一个性质参见鏼爷的PPT
不想翻就直接看结论吧 对于一个串的所有border，它们组成不超过logn个等差数列
也就是说，对于所有增加长度的方式（其实就是period），可以分成logn组，每组是一个等差数列
考虑怎么利用这个性质
假设只有一个等差数列k+i*d，长度为c，我们直接拿首项作为的模数，k就被消掉了!
对于一个点x假如去更新别人，它可以更新到的就是x+（1~c-1）*d这些点
想象一下，x不停往前走d，根据同余的性质，一定会成环，而总共互不相交的环是gcd(k,d)个的
我们可以把每个环分开做，总共的点数是O(n)的
考虑对于一个环，它最小的那个点是不会被更新的，那么从这个点断开，对于每个点能够对它贡献的就是它在环上的前面c-1个点
设在模k意义下能够被表示出的最小值为f[0~k-1]
f[i]=min(f[i],f[j]+k+(i-j)*d)这个上一个单调队列就完事了
多个等差数列？
如果我们能改变模数保证正确性，那这个题就完事了
事实上就是可以
考虑模数由m变成n，设在模m意义下能够被表示出的最小值为f[0~m-1]，在模n意义下能够被表示出的最小值为g[0~n-1]
这个时候，一步走n又变成有用的走法了（一步走m不行了，但是会在做的过程中被模掉就不管了）
先抛开这个不谈，直接先g[f[i]%n]=min(g[f[i]%n],f[i])，由于f对于m最小，在不考虑走n个情况下g也是最优的
考虑走n的贡献，其实是和一个等差数列去更新是同理的，找到最小位置断开，f[i]=min(f[i],f[j]+(i-j)*n)，不用单调队列直接递推就可以了，因为如果i-1没有被更新一定是i-1更优，i-1被更新相当于i从更前面转移过来
坑点：
我都要哭了 谁在UOJ写hash谁傻逼啊!!!!! 狂交17发选手在线等死，假如hash底数太大还会被卡T，我真是****
不要像我一样老老实实的把border按2次幂划分，这样是严格nlogn的，会被卡成80。。。直接能插就插。。。。那个logn会变得**一样小（不知所措）
给个福利，把UOJ第9个点的构造思路放这（我hash被卡死自己找规律玩出来的），就是开始串中只有一个a，然后按以下步骤做18次：把这个串复制一份，然后翻转，当当前是进行该步骤的奇数次时，把这个复制的串按位取反(a变成b b变成a)，然后接在原来的串后面，成为新的串
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath> #define min(x,y) (x<y?x:y)
#define ad(p,lim) ((p==lim)?1:p+1)
using namespace std;
typedef long long LL;
const int _=1e2;
const int maxn=*1e5+_;
const int mbit=;
LL inf;
int gcd(int a,int b)
{
if(a==)return b;
return gcd(b%a,a);
} //-------------------------------------def---------------------------------------------- char ss[maxn]; struct SSS
{
int k,d,c;//首项 公差 项数
SSS(){} SSS(int K,int D,int C){k=K,d=D,c=C;}
}s[maxn];int slen;
bool cmp(SSS s1,SSS s2){return s1.k<s2.k;}
int Log[maxn]; int p[maxn];
void getseq(int n)
{
int j=; p[]=;
for(int i=;i<=n;i++)
{
while(j!=&&ss[i]!=ss[j+])j=p[j];
if(ss[i]==ss[j+])j++;
p[i]=j;
}
slen=; int i=n;
do
{
i=p[i];
if(slen==|| s[slen].d!=-&&(n-i)-(s[slen].k+(s[slen].c-)*s[slen].d)!=s[slen].d )
s[++slen]=SSS(n-i,-,);
else
{
s[slen].c++;
if(s[slen].c==)s[slen].d=(n-i)-s[slen].k;
}
}while(i!=);
sort(s+,s+slen+,cmp);
} //----------------------------------getseq------------------------------------------------ int hlen,h[maxn],hp;//放环的
int mo,now,pre;LL f[][maxn];//对于当前模数余数等于i的数中，能够被表示出的第一个数
int tim,v[maxn];
void changemod(int nem)
{
int i;
for(i=;i<nem;i++)f[pre][i]=inf;
for(i=;i<mo;i++)
if(f[now][i]!=inf)f[pre][f[now][i]%nem]=min(f[pre][f[now][i]%nem],f[now][i]); int gg=gcd(mo,nem),k,j,u;
for(i=;i<gg;i++)
{
hlen=,h[hlen]=i,hp=;
u=mo%nem;k=i+u;if(k>=nem)k-=nem;
while(k!=i)
{
h[++hlen]=k;
if(f[pre][k]<f[pre][h[hp]])hp=hlen;
k+=u;if(k>=nem)k-=nem;
} k=hp,j=hp+;if(j==hlen+)j=;
while(j!=hp)
{
f[pre][h[j]]=min(f[pre][h[j]],f[pre][h[k]]+mo);
k=j,j++;if(j==hlen+)j=;
}
}
mo=nem;
} int head,tail,list[maxn];
void work(int sk,int sd,int sc)
{
if(sc==)return ; int gg=gcd(mo,sd),i,j,k,u,dis;
for(i=;i<gg;i++)
{
hlen=,h[hlen]=i,hp=;
u=sd%mo;k=i+u;if(k>=mo)k-=mo;
while(k!=i)
{
h[++hlen]=k;
if(f[now][k]<f[now][h[hp]])hp=hlen;
k+=u;if(k>=mo)k-=mo;
} head=tail=;list[]=hp;
j=hp+;if(j==hlen+)j=;
while(j!=hp)
{
dis=j-list[head];if(dis<)dis+=hlen;
while(head<=tail&&dis>sc-)
{
head++;
if(head<=tail){dis=j-list[head];if(dis<)dis+=hlen;}
}
f[now][h[j]]=min(f[now][h[j]],f[now][h[list[head]]]+sk+(LL)dis*sd); dis=j-list[tail];if(dis<)dis+=hlen;
while(head<=tail&&f[now][h[list[tail]]]>=f[now][h[j]]-(LL)dis*sd)
{
tail--;
if(head<=tail){dis=j-list[tail];if(dis<)dis+=hlen;}
}
list[++tail]=j;
j++;if(j==hlen+)j=;
}
}
} //------------------------------------solve---------------------------------------------- int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
int n;LL W;
scanf("%d%lld",&n,&W);W-=n;gets(ss+);
gets(ss+);
getseq(n); now=,pre=;
memset(f,,sizeof(f));f[now][]=; inf=f[][];
mo=s[slen].k,work(s[slen].k,s[slen].d,s[slen].c);
for(int i=slen-;i>=;i--)
{
changemod(s[i].k);
swap(now,pre);
work(s[i].k,s[i].d,s[i].c);
} LL ans=,num=W/mo,uli=W-num*mo;
for(int i=;i<mo;i++)
if(f[now][i]<=W)ans=ans+num+(i<=uli)-f[now][i]/mo;
printf("%lld\n",ans);
} return ;
}