【?】吉利数字 [数位dp]

中国人喜欢数字6和8。特别地，一些人喜欢满足含有特定个数6和8的数。现在请求出，在区间[L,R]之间的第K大的含有X个6和Y个8的数。

输入的第一行包括4个数字，L,R,X,Y。

接下来的一行给出该组数据的询问数Q。

接下来Q行中，每行有一个整数K。

对于某个询问，输出一行，为对应的第K大的数。如果不存在这个数则输出“That's too bad!”

 

我终于了却了今日的心事QAQ 自己硬刚好久 写递推的太难受了

首先是转移的时候要注意判断一下

在递推写数位dp的时候要注意在最后枚举和x数位相同的数的时候判断一下这个数本身合不合法 QAQ我总忘这个

最后是注意开long long！！！

/*
10000000000000 50000000000000 0 1
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
#define ll long long
#define rg register
const int N=2000000000+5,pw=11,inf=0x3f3f3f3f,P=19650827;
ll a,b,x,y;
ll base[20],f[20][10][20][20];
template <class t>void rd(t &x)
{
    x=0;int w=0;char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=w?-x:x;
}

void pre(){
    base[0]=1ll;
    for(int i=1;i<=19;++i) base[i]=base[i-1]*10ll;
    for(int i=0;i<=9;++i) f[1][i][i==6][i==8]=1;
    for(int i=2;i<=19;++i)
    for(int j=0;j<=9;++j)
    for(int k=0;k<=9;++k)
    for(int h6=(j==6);h6<=i;++h6)
    for(int h8=(j==8);h8<=i-h6;++h8)
    f[i][j][h6][h8]+=f[i-1][k][h6-(j==6)][h8-(j==8)];
}

ll solve(ll xx){
    ll p=0,num[20],sum=0;
//    for(p=0;p<=13;++p) if(base[p]>x) break;
    while(xx) num[++p]=xx%10,xx/=10;
    for(int i=1;i<p;++i)
    for(int j=1;j<=9;++j)
    sum+=f[i][j][x][y];
    for(int i=1;i<num[p];++i)
    sum+=f[p][i][x][y];
    int c6=0,c8=0;
    for(int i=p-1;i>0;--i){
        c6+=(num[i+1]==6),c8+=(num[i+1]==8);
        if(c6>x||c8>y) break;
        for(int j=0;j<num[i];++j){
        if((c6==x&&j==6)||(c8==y&&j==8)) continue;
         sum+=f[i][j][x-c6][y-c8];
        }
    }
    return sum;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("nocows.out","w",stdout);
    rd(a),rd(b),rd(x),rd(y);
    pre();
    ll up,dw;dw=solve(a+1);
    up=solve(b+1);
    int q;rd(q);
    for(int i=1;i<=18;++i) printf("%lld ",f[i][1][0][1]);
    while(q--){
        ll k;rd(k);
        ll l=a,r=b,mid,ans=-1;
        if(k+dw>up) printf("That's too bad!\n");
        else{
              while(l<r){
            mid=(l+r)>>1;
               ll nw=solve(mid+1);
               if(nw<dw+k) l=mid+1;
               else r=mid,ans=1;
               }
        printf("%lld\n",l);
        }
    }
    return 0;
}