题解 P4950 【完美数字】

· · 题解

来一个dfs版的数位dp。

这种统计和的数位dp，相对于统计个数的数位dp，既要记录个数，又要记录和。然后对于每一位，累加个数乘以这一位位置的贡献，即百位就是个数乘以100，千位就是乘以1000，依此类推。

有一个地方被坑了好久，不能用的数字我拿数组记下来，然后在枚举当前位的时候，没有判前导零，也就是如果零不能用，前导零我就不会枚举到。调了一年。。

没有什么思维难度，考察了数位dp模板的掌握程度。

Code\ Below: 
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define int long long
#define hh puts("")
#define pc putchar
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
int s1,s2,nd,no,l,r,a[15],mi[15];
struct node{
    int cnt,sum;
}dp[16][1<<10];
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+(ch^48);ch=getchar();}
    return ret*ff;
}
void write(int x){if(x<0){x=-x,pc('-');}if(x>9) write(x/10);pc(x%10+48);}
void writeln(int x){write(x),hh;}
void writesp(int x){write(x),pc(' ');}
node dfs(int pos,int zt,int lead,int lim){
    if(!pos){
        if((zt&nd)==nd&&(zt&no)==0) return (node){1,0};
        return (node){0,0};
    }
    if(!lead&&!lim&&dp[pos][zt].sum!=-1) return dp[pos][zt];
    int mx=lim?a[pos]:9;
    node res=(node){0,0};
    for(int i=0;i<=mx;i++){
        node t;
        if(lead&&!i) t=dfs(pos-1,zt,1,lim&&(i==mx));
        else t=dfs(pos-1,zt|(1<<i),0,lim&&(i==mx));
        res.cnt+=t.cnt;
        res.sum+=t.sum+t.cnt*i*mi[pos-1];
    }
    if(!lead&&!lim) dp[pos][zt]=res;
    return res;
}
int work(int x){
    if(!x) return 0;
    int len=0;
    while(x){
        a[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1,1).sum;
}
signed main(){
    mi[0]=1;
    for(int i=1;i<=15;i++) mi[i]=mi[i-1]*10;
    int T=read();
    while(T--){
        memset(dp,-1,sizeof(dp));
        l=read(),r=read();
        nd=no=0;
        s1=read();
        for(int i=1;i<=s1;i++) nd|=1<<(read());
        s2=read();
        for(int i=1;i<=s2;i++) no|=1<<(read());
        writeln(work(r)-work(l-1));
    }
    return 0;
}