On the subject

Topic link :http://pjudge.ac/problem/21652

The main idea of the topic

Give a positive integer $k$, Please $n$ individual $x$ Satisfy $x\times (10^k-1)$ None of the digits in is $9$.

$1\le n\le 10^{18},1\le k\le 18$

Their thinking

The first is to gradually determine the answer from high to low , But direct violence is definitely troublesome , We consider doing the opposite .

We count the first $n$ Legal $x\times (10^k-1)$, Then divide by $10^k-1$.

Now the problem is to give some definite bits , Find out how many kinds of bits are left without $9$ Can spell $10^k-1$ Multiple .

Then a number $10^k-1$ The condition of multiple of is to put it every $k$ Bit segmentation is proposed to sum at one time , If it is $10^k-1$ The multiple of is legal .

There won't be too many paragraphs , We can enumerate violence $10^k-1$ Multiple , And then the numbers dp solve .

There are a lot of details .

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll __int128
using namespace std;
const int W=40;
int k,a[80],b[80];
ll n,f[80][10];
ll read(){
    
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){
    if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void print(ll x)
{
    if(x>9)print(x/10);putchar(x%10+'0');return;}
ll solve(){
    
	int L=(W+k-1)/k;ll pw=1,ans=0;
	for(int i=1;i<=k;i++)pw=pw*(ll)10;pw--;
	for(int d=1;d<=L;d++){
    
		ll p=d*pw;
		for(int i=0;i<k;i++)
			b[i]=p%10,p/=10;
		memset(f,0,sizeof(f));f[0][0]=1;
		for(int i=0;i<k;i++){
    
			for(int z=0;z<L;z++)
				for(int x=(z==0);x<10;x++)
					f[z/10][z%10]+=f[z][x],f[z][x]=0;
			for(int j=0;j<L;j++)
				for(int z=L-1;z>=0;z--)
					for(int x=9;x>=0;x--){
    
						if(!f[z][x])continue;
						ll r=f[z][x];f[z][x]=0;
						if(a[j*k+i]==-1)
							for(int y=8;y>=0;y--)
								f[z+(x+y)/10][(x+y)%10]+=r;
						else 
							f[z+(x+a[j*k+i])/10][(x+a[j*k+i])%10]+=r;
					}
			for(int z=0;z<L;z++)
				for(int x=0;x<10;x++)
					if(x!=b[i])f[z][x]=0;
		}
		for(int x=0;x<10;x++)ans+=f[p][x];
	}
	return ans;
}
signed main()
{
    
	k=read();n=read();
	ll now=0,las;int m=(W+k-1)/k*k;
	for(int i=0;i<m;i++)a[i]=-1;
	for(int i=m-1;i>=0;i--){
    
		a[i]=0;now+=(las=solve());
		while(now<n){
    
			a[i]++;
			now+=(las=solve());
		}
		now-=las;
	}
	ll ans=0;//print(now);
	for(int i=m-1,flag=0;i>=0;i--)
		ans=ans*(ll)10+a[i];
	ll pw=1;
	for(int i=0;i<k;i++)pw=pw*(ll)10;
	pw=pw-1;ans/=pw;
	print(ans);
	return 0;
}
//1 8