题目链接
这个是一个二份答案的数位dp，注意开longlong。
#include <iostream>
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int b[121];
LL dp[121][2][2];
int tot,cnt;
long long n,L,R,a;
LL dfs(int pos,int preok,int pre1,int pre0)
{if(pos==-1) return pre0==0;if(preok&&dp[pos][pre1][pre0]!=-1) return dp[pos][pre1][pre0];int up=preok?1:b[pos];LL sum=0;for(int i=0;i<=up;i++){if(!(pre1&&i==1))sum+=dfs(pos-1,preok||i<b[pos],i==1,pre0&&i==0);}if(preok) dp[pos][pre1][pre0]=sum;return sum;
}
LL solve(LL R)
{tot=0;while(R){b[tot++]=R&1;R>>=1;}LL sum=dfs(tot-1,0,0,1);return sum;
}int main()
{memset(dp,-1,sizeof(dp));cin>>n;for(int i=1;i<=n;i++){cin>>a;L=1;R=1000000000000000001;while(L<R) {LL mid = (L + R) / 2;if (solve(mid) >= a) R = mid;else L = mid + 1;}cnt=0;while(L){b[cnt++] = L & 1;L >>= 1;}for (int i=cnt-1; i>=0; i--) printf("%d", b[i]);printf("\n");}
}