【洛谷P4950】完美数字 | Mrsrz's blog

状压数位 DP

题目大意：

给定数字集合 $S$ 和数字集合 $T$。问 $[l,r]$ 中所有满足以下条件的数 $x$ 之和。

• 数字集合中的所有数字都出现在 $x$ 的数位中。
• 不存在一个数位是数字集合 $T$ 中的数字。

保证 $S$ 与 $T$ 无交集且元素不会重复。

题解：

思路比较简单，就是把当前已经出现的 $S$ 中的元素状压起来，然后进行数位 dp。

这道题目采用预处理后面 $w$ 位任意填的情况，然后从高位往低位考虑，枚举每一位的值，然后后面的位直接使用预处理的答案计算的方法比较简单，且效率高。

令 $f[s][w]$ 表示 $w$ 位数，$S$ 中的元素出现的情况为 $s$ 的符合条件的数的和（这里考虑前导零），$g[s][w]$ 表示上述条件下的数的个数。

统计答案的时候，设当前的数有 $W$ 位，那么我们首先处理不足 $W$ 位的数的贡献。枚举位数，枚举最高位的数，然后通过 $f$ 和 $g$ 就可以计算答案。

接下来考虑 $W$ 位的数，从高位往低位枚举，枚举到第 $i$ 位的时候，更高位已经和最大值相等。则后面的数的所有情况，也可以用 $f$ 和 $g$ 的答案求得。

时间复杂度上界为 $O(2^{|S|}\times 100\times t)$。由于实际运行效率和 $l,r$ 的数位上的值有关，在测试数据上跑得飞快。实际上是有方法卡到比较慢的。但这仍是正确的复杂度。

Code：

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
int tt,l,r,S[11],T[11],tot,C;
const int W[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
LL f[1024][10],g[1024][10];
void work(int w){
    if(w==0){
        for(int i=0;i<10;++i)
        if(!T[i]){
            if(S[i]!=-1)
            ++g[1<<S[i]][0],f[1<<S[i]][0]+=i;else
            ++g[0][0],f[0][0]+=i;
        }
    }else{
        work(w-1);
        for(int i=0;i<=C;++i)
        for(int s=0;s<10;++s)
        if(!T[s]){
            int zt=i;
            if(S[s]!=-1)zt|=1<<S[s];
            g[zt][w]+=g[i][w-1];
            f[zt][w]+=g[i][w-1]*W[w]*s+f[i][w-1];
        }
    }
}
inline LL ask(int n){
    int w=0;
    for(int i=0;i<10;++i)
    if(n>=W[i])w=i;
    LL ret=0;
    for(int i=w-1;i>=0;--i){
        for(int s=1;s<10;++s)
        if(!T[s]){
            ret+=s*W[i]*(i?g[C][i-1]:(tot==0?1:0))+(i?f[C][i-1]:0);
            if(S[s]!=-1)ret+=s*W[i]*(i?g[C^(1<<S[s])][i-1]:((1<<S[s])==C))+(i?f[C^(1<<S[s])][i-1]:0);
        }
    }
    int sm=0,ss=0;
    for(int i=w;i>=0;--i){
        int wg=n/W[i]%10;
        for(int s=(i==w)?1:0;s<wg;++s)if(!T[s]){
            int zt=ss,sum=sm+W[i]*s;if(S[s]!=-1)zt|=1<<S[s];
            if(i==0)ret+=(zt==C)?sum:0;else
            for(int ww=0;ww<=C;++ww)if((zt|ww)==C){
                ret+=sum*g[ww][i-1]+f[ww][i-1];
            }
        }
        sm+=wg*W[i];
        if(T[wg])return ret;
        if(S[wg]!=-1)ss|=1<<S[wg];
    }
    if(ss==C)ret+=sm;
    return ret;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(cin>>tt;tt--;){
        memset(S,-1,sizeof S);
        memset(T,tot=0,sizeof T);
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        cin>>l>>r;
        int x,y;
        for(cin>>x;x--;){
            cin>>y;
            S[y]=tot++;
        }
        C=(1<<tot)-1;
        for(cin>>x;x--;){
            cin>>y;
            T[y]=1;
        }
        work(9);
        cout<<ask(r)-ask(l-1)<<'\n';
    }
    return 0;
}