数位dp预处理之后,可以容易得到f(x),代表小于等于x的数中,有多少个不含13的。然后就能二分答案啦。
#include<cstdio>
#include<iostream>
using namespace std;
typedef unsigned long long ull;
ull n;
ull f[19][3];
void init()
{
f[0][0]=1;
for(int i=1;i<=18;++i)
{
f[i][0]=f[i-1][0]*10-f[i-1][1];
f[i][1]=f[i-1][0];
f[i][2]=f[i-1][2]*10+f[i-1][1];
}
}
ull work(ull x)
{
ull ans=0,t=x,bit[25],len=0;
while(t)
{
bit[++len]=t%10;
t/=10;
}
ull is=1;
for(int i=len;i>1;--i){
if(bit[i]==1 && bit[i-1]==3){
is=0;
break;
}
}
bit[len+1]=bit[len+2]=0;
bool flag=0;
for(int i=len;i;--i)
{
if(bit[i+1]==3 && bit[i+2]==1)
flag=1;
ans+=f[i-1][2]*bit[i];
if(flag)
ans+=bit[i]*f[i-1][0];
else
{
if(bit[i] > 1)
ans+=f[i-1][1];
if(bit[i+1] == 1 && bit[i] > 3)
ans+=f[i][1];
}
}
return x-ans+is-1;
}
int T;
int main()
{
init();
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
scanf("%d",&T);
// work(14);
for(;T;--T)
{
cin>>n;
ull l=1,r=(ull)2000000000000000000ll;
while(l<r){
ull mid=(l+r)/(ull)2;
if(work(mid)>=n){
r=mid;
}
else{
l=mid+1;
}
}
cout<<l<<endl;
}
return 0;
}