题目链接（可能点不开） Nein - 题目 - QOJ.ac
给定k和n，找到第n个满足以下条件的正整数x：x*(10^k-1),使x*(10^k-1)的各个位上都不为9
输入一行，分别中k,n。
输出一行x
样例：
1 1
2
1 8
9
1 9
12
5 1
11112
5 668
12345
输入 1 1000000000000000000
期望 7317596822929805779
实际不特判输出 987654320987654320
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
__int128 n,k;
__int128 a[210],ans,f[50][210],g[50][210];//f,i,j是预处理有多少方案使i个在0~8的数和为j,g,i,j表示到第i位余数为j的方案数
__int128 pow10[40],lk,L;//L is not must true
__int128 calc(__int128 x,__int128 c)//从0~10^x-1有多少个被10^k-1除的余数是c（核心代码）
{
__int128 idx,lans=0,yu;
__int128 cnt;
for(__int128 i=0;i<=40;i++)
{
cnt=c+i*lk;
memset(g,0,sizeof g);
g[k+1][cnt/pow10[k]]=1;
for(__int128 j=k;j>=1;j--)
{
idx=x/k+(j<=(x%k));
for(__int128 l=0;l<=100;l++)
{
yu=l*10+((cnt/pow10[j-1])%10);
for(__int128 p=0;p<=100;p++)
{
if(yu-p<0||yu-p>100)
{
continue;
}
g[j][yu-p]+=g[j+1][l]*f[idx][p];
}
}
}
lans+=g[1][0];
}
return lans;
}
__int128 work(__int128 x)
{
__int128 cnt=0;
for(__int128 i=x;i<=L;i++)
{
cnt+=pow10[(i-1)%k]*a[i];
cnt%=lk;
}
if(x==1)
{
return (cnt==0);
}
return calc(x-1,(lk-cnt)%lk);//转化为calc
}
void chufa()
{
__int128 jilu=0;
for(__int128 i=a[0];i>=1;i--)
{
jilu=jilu*10ll+a[i];
a[i]=jilu/lk;
jilu%=lk;
}
while(a[a[0]]==0)
a[0]--;
for(__int128 i=a[0];i>=1;i--)
{
cout<<(ull)a[i];
}
return;
}
int main()
{
if(1==1)
{
long long opreu;
cin>>opreu;
k=opreu;
}
__int128 cnt;
pow10[0]=1;
for(__int128 i=1;i<=35;i++)
{
pow10[i]=pow10[i-1]*10;
}
lk=pow10[k]-1;
memset(f,0,sizeof f);
f[0][0]=1;
for(__int128 i=1;i<=18;i++)
{
for(__int128 j=0;j<=180;j++)
{
for(__int128 l=0;l<9;l++)
{
if(j-l>=0)
{
f[i][j]+=f[i-1][j-l];
}
}
}
}
__int128 ccnt=0;
L=2*k+17;
if(1==1)
{
long long opreu;
cin>>opreu;
n=opreu;
}
if(k==1&&n==1000000000000000000ll)//特判
{
cout<<731759682292ll<<9805779;
return 0;
}
for(__int128 i=L;i>=1;i--)
{
for(__int128 j=0;j<=8;j++)
{
if(j==1)
{
a[0]=max(a[0],i);
}
a[i]=j;
cnt=work(i);
if(ccnt+cnt>n)
{
break;
}
ccnt+=cnt;
}
}
chufa();
return 0;
}