2020-09-08数位DP二分

http://icpc.upc.edu.cn/problem.php?cid=2573&pid=6

题目描述

Tom is very interested in number problem. Nowadays he is thinking of a problem about A-number and B-number.

A-number is a positive integer whose decimal form contains 7 or it can be divided by 7. We can write down the first 10 A-number ( a[i] is the ith A-number)

{a[1]=7,a[2]=14,a[3]=17,a[4]=21,a[5]=27,a[6]=28,a[7]=35,a[8]=37,a[9]=42,a[10]=47};

B-number is Sub-sequence of A-number which contains all A-number but a[k] ( that k is a A-number.) Like 35, is the 7^th A-number and 7 is also an A-number so the 35 ( a[7] ) is not a B-number. We also can write down the first 10 B-number.

{b[1]=7,b[2]=14,b[3]=17,b[4]=21,b[5]=27,b[6]=28,b[7]=37,b[8]=42,b[9]=47,b[10]=49};

Now Given an integer N, please output the Nth B-number.

输入

The input consists of multiple test cases.

For each test case, there will be a positive integer N as the description.

输出

For each test case, output an integer indicating the Nth B-number.

You can assume the result will be no more then 2^63-1.

样例输入

1
7
100

样例输出

7
37
470

数位DP+二分查找 https://www.cnblogs.com/shinecheng/p/3601235.html https://blog.csdn.net/weixin_33827965/article/details/93230896

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll; ///2^63-1 建议用unsigned long long 
ll newx;
ll number[1005]={0};
ll dp[1005][1005]={0};
ll power[300]={0};
inline ll dfs(ll i,ll mod,int lim) ///lim为标记是否有上限
{
    if(i==0)
        return mod==0;
    if(!lim&&~dp[i][mod])  /// ~(-1)=0
        return dp[i][mod];
    int end1=lim?number[i]:9;
    ll ans=0;
    for(int j=0;j<=end1;j++)
    {
        if(j!=7)
            ans+=dfs(i-1,(mod-(j*power[i-1])%7+7)%7,lim&&j==end1);  ///取余为7的情况
        else if(j==7)
            ans+=(lim&&j==end1)?(newx%power[i-1]+1):power[i-1]; ///首位为7的情况
    }
    if(!lim) ///没有限制
        dp[i][mod]=ans;
    return ans;
}
ll js(ll p)
{
    newx=p;
    if(p==0)
        return 0;
    int k=0;
    while(p!=0)
    {
        number[++k]=p%10;
        p=p/10;
    }
    return dfs(k,0,1)-1;
}
ll out(ll n)
{
    ll l=1,r=(1ll<<63)-1;
    while(l<r)
    {
        ll mid=(l+r)/2;;
        ll a=js(mid);
        ll b=a-js(a);
        if(b>=n)
            r=mid;
        else
            l=mid+1;
    }
    return l;
}
int main()
{
    power[0]=1;
    for(int i=1;i<=100;i++)
        power[i]=power[i-1]*10;
    ll n;
    for(int i=0;i<200;i++)
        for(int j=0;j<200;j++)
            dp[i][j]=-1;
    while(scanf("%lld",&n)!=EOF)
        printf("%lld\n",out(n));
}