题意

分析

考场爆零做法

考虑位数少的一定更小，高位小的一定更少。

然后计算一定位数下不同数字的个数，然后从高到低依次确定数位。

特例：如果确定的高位的后缀出现了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(0,\textrm{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;

}