题意：有一个序列a，a中的每个元素的每一位都不为4，问序列中第k个数字是多少。
分析：可以用数位dp查询出1-r中有多少个满足条件的数字，通过二分r找到结果。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' using namespace std; typedef long double ld; typedef pair<int, int> pii; typedef pair<int,pair<int,int>> pil; typedef unsigned long long ULL; const ll mod = 1e9+7; const int M=1e5+5; const int N = 3e5+ 5; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } int cmp(int a, int b) { return a > b; } int a[20],len=0; ll f[20]; ll dfs(int pos,bool limit) { if(!pos) return (ll)1; if(!limit&&f[pos]!=-1) return f[pos]; ll res=0; int up=limit?a[pos]:9; for(int i=0;i<=up;i++) { if(i==4) continue; res+=dfs(pos-1,limit&&(i==up)); } if(!limit) f[pos]=res; return res; } ll get(ll x) { len=0; while(x) { a[++len]=x%10; x/=10; } memset(f,-1,sizeof(f)); return dfs(len,true); } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t; cin>>t; while(t--) { ll k; cin>>k; ll l=k,r=1e18; while(l<r) { ll mid=(l+r)/2; if(get(mid)-1>=k) r=mid; else l=mid+1; } cout<<r<<endl; } }