考虑每一次增加的长度,显然是形如$n-border$,同时总可以取到
换言之,记$a_{i}$为所有$n-border$的值,问题即求有多少个$l\in [0,w-n]$使得$\exists x_{i}\in N^{},\sum_{i=1}^{m}a_{i}x_{i}=l$
根据border的性质,$a_{i}$可以被划分为$o(\log n)$个等差数列,具体证明略
记第$i$个等差数列为$\{x_{i}+kd_{i}\mid k\in [0,l_{i})\}$,(依次)求出前$i$个等差数列模$x_{i}$的同余最短路
考虑转移,分为两部分:
1.将模$x_{i-1}$的同余最短路变为模$x_{i}$的同余最短路
2.加入第$i$个等差数列中的元素
记模$x_{i-1}$的同余最短路答案为$g_{i}$,转换为模$x_{i}$的同余最短路即
$$
f_{g_{j}\ mod\ x_{i}}=\min g_{j},f_{j}=\min f_{(j-x_{i-1})\ mod\ x_{i}}+x_{i-1}
$$
关于这个过程,前者直接枚举$g_{j}$,后者即拆为了$\gcd(x_{i-1},x_{i})$个环,每一个环可以在(当前)最小值处断开
进一步的,加入第$i$个等差数列中的元素,即
$$
f_{j}=\min_{0\le k<l_{i}}f_{(j-kd_{i})\ mod\ x_{i}}+(x_{i}+kd_{i})
$$
关于这个过程,类似之前的处理方式,断开环后使用单调队列维护即可
当$i=n$时,所得到的即全局模$x_{n}$的同余最短路,进而可以求出答案
最终,总复杂度为$o(n\log n)$,可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 #define ll long long 5 int t,n,m,x0,nex[N],a[N]; 6 ll w,ans,g[N],f[N]; 7 char s[N]; 8 pair<int,ll>q[N]; 9 void add(int x,int l,int d){ 10 if (!x0){ 11 memset(f,0x3f,sizeof(f)); 12 f[0]=0; 13 } 14 else{ 15 memcpy(g,f,sizeof(g)); 16 memset(f,0x3f,sizeof(f)); 17 for(int i=0;i<x0;i++)f[g[i]%x]=min(f[g[i]%x],g[i]); 18 int D=__gcd(x,x0); 19 for(int i=0;i<D;i++){ 20 int pos=i; 21 for(int j=(i+x0)%x;j!=i;j=(j+x0)%x) 22 if (f[j]<f[pos])pos=j; 23 int lst=pos; 24 for(int j=(pos+x0)%x;j!=pos;j=(j+x0)%x){ 25 f[j]=min(f[j],f[lst]+x0); 26 lst=j; 27 } 28 } 29 } 30 x0=x; 31 if (l==1)return; 32 int D=__gcd(d,x); 33 for(int i=0;i<D;i++){ 34 int pos=i,L=0,R=0; 35 for(int j=(i+d)%x;j!=i;j=(j+d)%x) 36 if (f[j]<f[pos])pos=j; 37 q[0]=make_pair(0,f[pos]); 38 for(int j=(pos+d)%x,k=1;j!=pos;j=(j+d)%x,k++){ 39 while ((L<=R)&&(q[L].first<=k-l))L++; 40 if (L<=R)f[j]=min(f[j],q[L].second+k*d+x); 41 while ((L<=R)&&(f[j]-k*d<q[R].second))R--; 42 q[++R]=make_pair(k,f[j]-k*d); 43 } 44 } 45 } 46 int main(){ 47 scanf("%d",&t); 48 while (t--){ 49 scanf("%d%lld%s",&n,&w,s+1),w-=n; 50 m=x0=ans=nex[0]=nex[1]=0; 51 for(int i=2,j=0;i<=n;i++){ 52 while ((j)&&(s[j+1]!=s[i]))j=nex[j]; 53 if (s[j+1]==s[i])j++; 54 nex[i]=j; 55 } 56 for(int i=nex[n];;i=nex[i]){ 57 a[++m]=n-i; 58 if (!i)break; 59 } 60 for(int i=1,j=1;i<=m;i++) 61 if ((i==m)||(a[j+1]-a[j]!=a[i+1]-a[i])){ 62 add(a[j],i-j+1,a[j+1]-a[j]); 63 j=i+1; 64 } 65 for(int i=0;i<x0;i++) 66 if (f[i]<=w)ans+=(w-f[i])/x0+1; 67 printf("%lld\n",ans); 68 } 69 return 0; 70 }View Code