題意：給m，n，問含有m個0的第k個數，是幾位數，並且最高位是多少。
思路：和普通數位dp一樣，加上個二分。
然後就是注意一下，極限值測試下能否算出來，這題極限值很大！
代碼：
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
//2014年9月24日17:07:38
__int64 dp[22][22][11];
int num[22];
__int64 dfs(int site,int n,int m,int zero,int f)
{
if(site==0)
{
if(zero) return 0;
return n==m?1:0;
}
if(!f&&!zero&&~dp[site][n][m]) return dp[site][n][m];
int len=f?num[site]:9;
__int64 ans=0;
for(int i=0; i<=len; i++)
{
if(zero) ans+=dfs(site-1,n,m,zero&&i==0,f&&i==len);
else
{
if(i==0) ans+=dfs(site-1,n+1,m,zero&&i==0,f&&i==len);
else ans+=dfs(site-1,n,m,zero&&i==0,f&&i==len);
}
}
if(!f&&!zero) dp[site][n][m]=ans;
return ans;
}
__int64 solve(__int64 x,int m)
{
if(x<0) return 0;
int cnt=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
return dfs(cnt,0,m,1,1);
}
int main()
{
int t;
cin>>t;
memset(dp,-1,sizeof(dp));
while(t--)
{
__int64 k;
int m;
scanf("%d%I64d",&m,&k);
__int64 l=1,r=9000000000000000000LL,mid,ans;
while(l<=r)
{
mid=(l+r)/2;
if(solve(mid,m)>=k)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
__int64 len,tt=1,n;
len=(__int64)log10(ans*1.0)+1;
n=len-1;
while(n--) tt*=10;
printf("%I64d %I64d\n",len,ans/tt);
//printf("%I64d\n",ans);
}
return 0;
}
//2014年9月24日18:07:25
