K-th Nya Number
Time Limit: 1000ms
Memory Limit: 65536KB
This problem will be judged on HDU. Original ID: 3943
64-bit integer IO format: %I64d Java class name: Main
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.
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).
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).
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!
Source
解题：数位dp+二分
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int maxn = ;
LL dp[maxn][maxn][maxn];
int bt[maxn],x,y;
LL dfs(int len,int a,int b,bool flag){
if(len == -) return a == x && y == b;
if(!flag && dp[len][a][b] != -) return dp[len][a][b];
int u = flag?bt[len]:;
LL ans = ;
for(int i = ; i <= u; ++i){
if(i == ) ans += dfs(len-,a + ,b,flag&&i == u);
else if(i == ) ans += dfs(len-,a,b + ,flag&&i==u);
else ans += dfs(len-,a,b,flag&&i==u);
}
if(!flag) dp[len][a][b] = ans;
return ans;
}
LL solve(LL x){
int cnt = ;
while(x){
bt[cnt++] = x%;
x /= ;
}
return dfs(cnt - ,,,true);
}
int main(){
int kase,m,cs = ;
scanf("%d",&kase);
while(kase--){
LL P,Q,K;
scanf("%I64d%I64d%d%d",&P,&Q,&x,&y);
memset(dp,-,sizeof dp);
scanf("%d",&m);
printf("Case #%d:\n",cs++);
LL tmp = solve(P);
while(m--){
scanf("%I64d",&K);
K += tmp;
LL low = P + ,high = Q,ans = -;
while(low <= high){
LL mid = (low + high)>>;
if(solve(mid) >= K){
ans = mid;
high = mid - ;
}else low = mid + ;
}
if(ans == -) puts("Nya!");
else printf("%I64d\n",ans);
}
}
return ;
}