传送门
题意：
给444个整数L,R,K,nL,R,K,nL,R,K,n，和nnn个数字串，L,R,K,数字串大小≤1e18,n≤65L,R,K,数字串大小\le1e18,n\le65L,R,K,数字串大小≤1e18,n≤65
问[L,R][L,R][L,R]中第KKK小的拥有nnn个数字串中至少一个串作为子串的数。
思路：
一看就要二分答案，现在考虑统计[L,R][L,R][L,R]中有多少个满足题意的数。
不妨考虑数位dpdpdp，然后发现没法很好的转移，为了优化转移可以对于所有的数字串构建一个acacac自动机来优化转移。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=2005;
typedef long long ll;
namespace acam{
int ch[N][10],fail[N],tot=0,q[N],hd,tl;
bool exi[N];
#define idx(x) ((x)^48)
inline void init(){memset(ch[0],0,sizeof(ch[0])),memset(fail,0,sizeof(fail)),exi[0]=0,tot=0;}
inline int build(){return exi[++tot]=0,memset(ch[tot],0,sizeof(ch[tot])),tot;}
inline void insert(char s[]){
int p=0,n=strlen(s);
for(ri x,i=0;i<n;++i){
if(!ch[p][(x=idx(s[i]))])ch[p][x]=build();
p=ch[p][x];
}
exi[p]=1;
}
inline void getfail(){
hd=1,tl=0;
for(ri i=0;i<10;++i)if(ch[0][i])q[++tl]=ch[0][i];
while(hd<=tl){
int p=q[hd++];
for(ri i=0,v;i<10;++i){
if((v=ch[p][i]))fail[v]=ch[fail[p]][i],q[++tl]=v,exi[v]|=exi[fail[v]];
else ch[p][i]=ch[fail[p]][i];
}
}
}
#undef idx
}
namespace dDP{
ll f[20][N][2];
vector<int>Up,Down;
inline vector<int>init(ll x){
vector<int>ret;
ret.clear();
if(!x)return ret.push_back(x),ret;
while(x)ret.push_back(x-x/10*10),x/=10;
return ret;
}
inline ll dfs(int pos,int sta,bool flag,bool down,bool up,bool zero){
if(pos==-1)return flag;
if(!up&&!down&&!zero&&~f[pos][sta][flag])return f[pos][sta][flag];
ll ret=0;
for(ri l=down?Down[pos]:0,r=up?Up[pos]:9,i=l;i<=r;++i){
if(zero&&!i&&pos)ret+=dfs(pos-1,0,flag,down&&i==l,up&&i==r,1);
else ret+=dfs(pos-1,acam::ch[sta][i],flag|acam::exi[acam::ch[sta][i]],down&&i==l,up&&i==r,zero&&!i);
}
if(!up&&!down&&!zero)f[pos][sta][flag]=ret;
return ret;
}
inline ll solve(ll l,ll r){
int len1,len2;
Down=init(l),len1=Down.size();
Up=init(r),len2=Up.size();
for(ri i=len1+1;i<=len2;++i)Down.push_back(0);
return dfs(Up.size()-1,0,0,1,1,1);
}
}
char s[100];
int main(){
ll a,b,K,l,r,ans;
int n;
cin>>a>>b>>K>>n;
acam::init();
while(n--)scanf("%s",s),acam::insert(s);
acam::getfail();
l=a,r=b+1,ans=b+1;
memset(dDP::f,-1,sizeof(dDP::f));
while(l<=r){
ll mid=l+r>>1;
if(dDP::solve(a,mid)<K)l=mid+1;
else r=mid-1,ans=mid;
}
if(ans==b+1)puts("no such number");
else cout<<ans;
return 0;
}