记录编号	231763	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZOJ 2599]高级字典序	最终得分	100
用户昵称	张灵犀不和我一般见识真可怕呢（笑	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2016-02-27 19:03:35	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEL=30,SIZEN=210;
typedef unsigned long long LL;
LL f[SIZEL][SIZEN]={0};//长度为L，数位和为N的数的个数
LL Pow10[SIZEL]={0};
void prepare()
{
	f[0][0]=1;
	for(int i=1;i<=20;i++)
	{
		f[i][0]=1;
		for(int j=1;j<=200;j++)
		{
			f[i][j]=0;
			for(int k=0;k<=9;k++)
			{
				if(j<k) break;
				f[i][j]+=f[i-1][j-k];
			}
		}
	}
	Pow10[0]=1;
	for(int i=1;i<=20;i++) Pow10[i]=10*Pow10[i-1];
}
int digsum(LL x)
{
	int ans=0;
	while(x)
	{
		ans+=x%10;
		x/=10;
	}
	return ans;
}
int dignum(LL x)
{
	int ans=0;
	while(x)
	{
		ans++;
		x/=10;
	}
	return ans;
}
LL calc(LL N,int s)//数位之和小于s且数的大小小于N
{
	int len=dignum(N);
	LL ans=0;
	if(digsum(N)==s) ans++;
	for(int i=len;i>=1;i--)
	{
		int now=(N/Pow10[i-1])%10;
		for(int j=0;j<now&&j<=s;j++)
		{
			ans+=f[i-1][s-j];
		}
		if(s<now) break;
		else s-=now;
	}
	return ans;
}
LL sum(LL N,LL K,int s)//如你所见，数位之和小于s且字典序小于K
{
	LL ans=0;
	int LK=dignum(K),LN=dignum(N);
	for(int i=1;i<s;i++) ans+=calc(N,i);
	if(K==0) return ans;
	LL tem=K;
	for(int i=LK;i>=1;i--)
	{
		ans+=calc(tem,s);
		ans-=f[i-1][s];
		tem/=10;
	}
	tem=K*10;
	for(int i=LK+1;i<=LN;i++)
	{
		ans+=calc(min(N,tem-1),s);
		ans-=f[i-1][s];
		tem*=10;
	}
	return ans;
}
LL getnumber(LL N,LL K)
{
	int i=1;
	LL tem=0;
	while(true)
	{
		LL now=calc(N,i);
		if(tem+now<K) tem+=now;
		else break;
		i++;
	}
	LL ans=0;
	int s=i;
	while(true)
	{
		ans*=10;
		int j=0;
		while(j<=9)
		{
			//cout<<ans+j<<" "<<sum(N,ans+j,s)<<endl;
			if(sum(N,ans+j,s)>=K) break;
			j++;
		}
		//cout<<ans<<" "<<j<<endl;
		ans=ans+j;
		//cout<<ans<<endl;
		if(sum(N,ans,digsum(ans))==K) break;
		ans--;
	}
	return ans;
}
void work()
{
	LL n,k;
	cin>>n>>k;
	cout<<sum(n,k,digsum(k))<<endl;
	cout<<getnumber(n,k)<<endl;
}
int main()
{
	freopen("Lexicographical.in","r",stdin);
	freopen("Lexicographical.out","w",stdout);
	prepare();
	work();
	return 0;
}