题意
分析
考场爆零做法
考虑位数少的一定更小，高位小的一定更少。
然后计算一定位数下不同数字的个数，然后从高到低依次确定数位。
特例：如果确定的高位的后缀出现了x，那么要把x调整到后缀去，这样一定更优。
然而这样做有问题，有重复的情况，譬如样例1的6666。
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=2e3+7;
char X[MAXN],ans[MAXN];
int len;
ll n;
int main()
{
freopen("python.in","r",stdin);
freopen("python.out","w",stdout);
scanf("%s",X+1);
len=strlen(X+1);
read(n);
if(n==1)
{
puts(X+1);
return 0;
}
n-=1;
int lim;
for(lim=1;;++lim)
{
ll sum=(ll)lim*9*pow(10,lim-1)+pow(10,lim);
cerr<<"lim="<<lim<<" sum="<<sum<<endl;
if(n>sum)
n-=sum;
else
break;
}
cerr<<"n="<<n<<" lim="<<lim<<endl;
for(int i=1;i<=lim;++i)
{
cerr<<"i="<<i<<endl;
for(int j=(i==1?1:0);j<=9;++j)
{
ll sum=(ll)(lim-i+1)*pow(10,lim-i);
// cerr<<" j="<<j<<" sum="<<sum<<endl;
if(n>sum)
n-=sum;
else
{
ans[i]=j+'0';
ans[i+1]=0;
break;
}
if(j==9)
abort();
}
cerr<<"ansi="<<ans[i]<<endl;
if(i>=len&&strcmp(ans+i-len+1,X+1)==0)
{
// cerr<<"n="<<n<<endl;
int j;
for(j=lim+len;n;--j,n/=10)
{
ans[j]=n%10+'0';
}
for(;j>i;--j)
{
ans[j]='0';
}
puts(ans+1);
return 0;
}
}
printf("%s%s",ans+1,X+1);
// fclose(stdin);
// fclose(stdout);
return 0;
}
标解
毕姥爷太强了。
匹配字符串，考虑自动机上dp。
构造对x的KMP自动机，只是末尾位置的trans均指向末尾。
那么如果数字中出现过x，自动机上跑出来一定在末尾位置。
记(f(i,j))表示从状态j走i步走到末尾位置上的方案数。写出转移方程：
[f(i,j)=sum_{k=0}^{9}f(i-1, extrm{trans}(j,k))
]
边界条件(f(0, extrm{maxstate})=1)
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x)
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return x=data*w;
}
typedef long long ll;
typedef unsigned long long ull;
const ll INF=(1ULL << 63) - 1;
const int MAXN=2e3+20;
char s[MAXN];
ll n;
int nx[MAXN];
int trans[MAXN][MAXN];
ull f[MAXN][MAXN];
int main()
{
freopen("python.in","r",stdin);
freopen("python.out","w",stdout);
scanf("%s",s+1);
int l=strlen(s+1);
// 处理next数组
int p=0;
for(int i=2;i<=l;++i)
{
while(p && s[p+1] != s[i])
{
p = nx[p];
}
if(s[p+1] == s[i])
{
++p;
}
nx[i]=p;
}
for(int i=0;i<l;++i) // 处理trans转移数组
for(int j=0;j<10;++j)
{
p = i;
while(p && s[p + 1] != j + '0')
{
p = nx[p];
}
if(s[p + 1] == j + '0')
{
++p;
}
trans[i][j] = p;
}
for(int i=0;i<10;++i)
{
trans[l][i]=l;
}
f[0][l]=1;
for(int i=1;i<2015;++i) // 2015是估计值
for(int j=0;j<=l;++j)
for(int k=0;k<10;++k)
{
f[i][j] += f[i-1][trans[j][k]];
if(f[i][j] > INF)
{
f[i][j] = INF;
}
}
read(n);
int lim;
for(lim=1;lim < 2015 && f[lim][0] < n;++lim);
p=0;
for(int i=lim,j;i;--i)
{
for(j=0;j<10;++j)
{
if(n > f[i-1][trans[p][j]])
n -= f[i-1][trans[p][j]];
else
break;
}
printf("%d",j);
p = trans[p][j];
}
puts("");
// fclose(stdin);
// fclose(stdout);
return 0;
}