HDU 3943 数位dp+二分

K-th Nya Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 125536/65536 K (Java/Others)
Total Submission(s): 3155    Accepted Submission(s): 1021

Problem Description

Arcueid likes nya number very much.
A nya number is the number which has exactly X fours and Y sevens(If X=2 and Y=3 , 172441277 and 47770142 are nya numbers.But 14777 is not a nya number ,because it has only 1 four).
Now, Arcueid wants to know the K-th nya number which is greater than P and not greater than Q.

 

Input

The first line contains a positive integer T (T<=100), indicates there are T test cases.
The second line contains 4 non-negative integers: P,Q,X and Y separated by spaces.
( 0<=X+Y<=20 , 0< P<=Q <2^63)
The third line contains an integer N(1<=N<=100).
Then here comes N queries.
Each of them contains an integer K_i (0<K_i <2^63).

 

Output

For each test case, display its case number and then print N lines.
For each query, output a line contains an integer number, representing the K_i-th nya number in (P,Q].
If there is no such number,please output "Nya!"(without the quotes).

 

Sample Input

1
38 400 1 1
10
1
2
3
4
5
6
7
8
9
10

 

Sample Output

Case #1:
47
74
147
174
247
274
347
374
Nya!
Nya!

 

Author

hzhua

题意：

求区间内第k个有且仅有x个4和y个7的数

代码：

//注意细节

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int t,x,y,bit[];

ll f[][][],P,Q;

ll dfs(int pos,int xx,int yy,int limit)

{

    if(pos==) return (xx==&&yy==);

    if(xx<||yy<) return ;

    if(!limit&&f[pos][xx][yy]!=-) return f[pos][xx][yy];

    int max_b=limit?bit[pos]:;

    ll ans=;

    for(int i=;i<=max_b;i++){

        ans+=dfs(pos-,xx-(i==),yy-(i==),limit&&(i==max_b));

    }

    if(!limit) f[pos][xx][yy]=ans;

    return ans;

}

ll solve(ll O)

{

    int pos=;

    while(O){

        bit[++pos]=O%;

        O/=;

    }

    return dfs(pos,x,y,);

}

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d",&t);

    for(int cas=;cas<=t;cas++){

        printf("Case #%d:\n",cas);

        memset(f,-,sizeof(f));

        scanf("%lld%lld%d%d",&P,&Q,&x,&y);

        ll tmp1=solve(P);

        ll tmp2=solve(Q);

        int n;ll k;

        scanf("%d",&n);

        while(n--){

            scanf("%lld",&k);

            if(tmp2-tmp1<k) { puts("Nya!");continue; }

            ll l=P+,r=Q,ans;

            while(l<=r){

                ll mid=(l+r)>>;

                ll tmp=solve(mid);

                if(tmp-tmp1>=k) { ans=mid;r=mid-; }

                else l=mid+;

            }

            printf("%lld\n",ans);

        }

    }

    return ;

}