题目链接
题意
有一个长为\(n\)的由小写字母组成的字符串，需要用小写字母再填\(m\)位，使最后的字符串中本质不同的子串数量尽量多，答案对\(10^9+7\)取模。
本题数据:\(n,m\le 10^6\)，事实上\(n\le10^6,m\le10^{18}\)也可以做
solution
先考虑\(m=0\)的情况，此时字符串确定，令\(f[i]\)表示前\(i\)位字符串中本质不同的子串数量，考虑到第\(i\)位时，新产生的子串是前\(i-1\)位所有本质不同的字符串最后接上第\(i\)位以及第\(i\)位自身。
于是\(f[i]=f[i-1]+f[i-1]+1\)，但如果\(a[i](i出的字母)\)，曾经在\(last[a[i]]\)处出现过，那么前\(last[a[i]]-1\)位字符串的子串与\(a[i]\)组合而成的字符串会重复，所以\(f[i]=f[i-1]+f[i-1]-f[last[a[i]-1]\)
当\(m>0\)时，为使答案最大，我们需要让靠前的\(last[a[i]]\)尽量小，所以填写时按\(last[i]\)从小到大依次填写一定最优，于是\(O(n+m)\)扫一遍，就可以通过CF645E此题。
发现填写序列时每\(k\)位一个循环，而\(k\le26\)，所以可以矩阵快速幂优化到\(O(n+k^3log(m))\)，能通过\(m\le10^{18}\)的数据
code
//O(n+m)算法
#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
const int N=2e6+10;
int n,m,k,a[N],vis[N],q[N],cnt,f[N],last[N],tot=0;
char s[N];
inline int add(int x,int y,int mod=M){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y,int mod=M){return (x-y<0)?x-y+mod:x-y;}
int main(){
scanf("%d%d",&m,&k);cnt=k;
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;++i) a[i]=s[i]-'a'+1;
for(int i=n;i>=1;--i)
if(!vis[a[i]]) q[--cnt]=a[i],vis[a[i]]=1;
for(int i=1;i<=k;++i) if(!vis[i]) q[--cnt]=i;
memset(last,-1,sizeof(last));
for(int i=1;i<=n+m;++i){
if(i>n) a[i]=q[tot],tot=add(tot,1,k);
if(last[a[i]]!=-1) f[i]=dec(add(f[i-1],f[i-1]),f[last[a[i]]-1]);
else f[i]=add(add(f[i-1],f[i-1]),1);
last[a[i]]=i;
}
printf("%d\n",f[n+m]+1);
return 0;
}
//O(n+k^3log(m))算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e9+7;
const int N=4e6+10;
const int K=210;
int n,k,a[N],vis[N],q[N],cnt,f[N],last[N],tot=0,pw[N];
ll m;
char s[N];
inline int add(int x,int y,int mod=M){return (x+y>=mod)?x+y-mod:x+y;}
inline int dec(int x,int y,int mod=M){return (x-y<0)?x-y+mod:x-y;}
struct matrix{
int c[K][K];
void build(int d=0){
for(int i=1;i<=k+1;++i)
for(int j=1;j<=k+1;++j) c[i][j]=0;
for(int i=1;i<=k+1;++i) c[i][i]=d;
}
matrix operator *(matrix x){
matrix ret;ret.build();
for(int i=1;i<=k+1;++i)
for(int j=1;j<=k+1;++j)
for(int w=1;w<=k+1;++w)
ret.c[i][j]=add(ret.c[i][j],1ll*c[i][w]*x.c[w][j]%M);
return ret;
}
};
matrix operator ^(matrix a,ll k){
matrix ret;ret.build(1);
while(k){
if(k&1) ret=ret*a;
a=a*a;k>>=1;
}
return ret;
}
int main(){
scanf("%lld%d",&m,&k);cnt=k;
scanf("%s",s+1);n=strlen(s+1);
for(int i=1;i<=n;++i) a[i]=s[i]-'a'+1;
for(int i=n;i>=1;--i)
if(!vis[a[i]]) q[--cnt]=a[i],vis[a[i]]=1;
for(int i=1;i<=k;++i) if(!vis[i]) q[--cnt]=i;
memset(last,-1,sizeof(last));
int t=min(m,k*1ll);
for(int i=1;i<=n+t;++i){
if(i>n) a[i]=q[tot],tot=add(tot,1,k);
if(last[a[i]]!=-1) f[i]=dec(add(f[i-1],f[i-1]),f[last[a[i]]-1]);
else f[i]=add(add(f[i-1],f[i-1]),1);
last[a[i]]=i;
}
if(m==t) printf("%d\n",f[n+m]+1);
else{
matrix A;A.build();
pw[0]=1;for(int i=1;i<=k+1;++i) pw[i]=2ll*pw[i-1]%M;
A.c[1][k+1]=1;
for(int i=2;i<=k+1;++i){
for(int j=1;j<i-1;++j)
A.c[i][j]=dec(M,pw[i-j-1]);
A.c[i][i-1]=M-1;
A.c[i][k+1]=add(A.c[i][k+1],pw[i-1]);
}
ll c=(m-1)/k,ans=0;m-=c*k;
A=A^c;
for(int i=0;i<=k;++i) ans=add(ans,1ll*f[n+i]*A.c[m+1][i+1]%M);
printf("%d\n",ans+1);
}
return 0;
}