数位DP

Defy_HeavenS · 2025-11-05 10:49:01 · 算法·理论

题目

1081. 度的数量 - AcWing题库 B 进制下是 01 串，利用二叉树的结构来考虑（按位分类讨论）。 1082. 数字游戏 - AcWing题库、P2657 [SCOI2009] windy 数 - 洛谷 设 f_{i,j} 表示长度位 i，最高位填 j 的数的个数。 P4127 [AHOI2009] 同类分布 - 洛谷 枚举模数。

P10958 启示录 - 洛谷

题面

对于一个数，若其十进制表示下出现了连续的三个 6，那么它就是魔鬼数。问第 x 小的魔鬼数，T 组数据。

题解

分析：首先试填法分析问题，确定需要解决的未知信息。那么要解决的未知信息就是，后边有多少种填发能产生魔鬼数？

预处理：设 f_{i,0/1/2/3} 表示由 i 位数字构成，开头是 0/1/2 个 6 的魔鬼数个数，特殊的，f_{i,3} 表示由 i 位数字构成的魔鬼数个数。

依次考虑这一位填的数是什么，和填这个数的贡献，可以简单的推出：

试填：从左到右试填，记录当前末尾连续的 6 的个数。从小到大枚举这一位填什么数，通过 f 求出这样能得到多少魔鬼数的填发，然后和 x 做对比，最后一位一位地确定出答案。

const LL N=20+5;
LL T,n,dp[N][4];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    dp[0][0]=1;
    for(LL i=1;i<=20;i++){
        dp[i][0]=9*(dp[i-1][0]+dp[i-1][1]+dp[i-1][2]);
        dp[i][1]=dp[i-1][0];
        dp[i][2]=dp[i-1][1];
        dp[i][3]=10*dp[i-1][3]+dp[i-1][2];
    }
    cin>>T;
    while(T--){
        cin>>n;
        LL len=3;
        while(dp[len][3]<n){
            len++;
        }
        for(LL i=len,k=0;i>=1;i--){
            for(LL j=0,cnt;j<=9;j++){
                cnt=dp[i-1][3];
                if(j==6||k==3){
                    for(LL l=max(3-k-(j==6),0ll);l<=2;l++){
                        cnt+=dp[i-1][l];
                    }
                }
                if(cnt<n){
                    n-=cnt;
                }else{
                    if(k<3){
                        if(j==6){
                            k++;
                        }else{
                            k=0;
                        }
                    }
                    cout<<j;
                    break;
                }
            }
        }
        cout<<"\n";
    }
    return 0;
}

P10959 月之谜 - 洛谷

题面

对于一个数，若它能被自己地数位和整除，那么它就是月之数。问区间 [l,r] 内有多少月之数，多组数据。

题解

分析：如果设 g(l,r) 表示区间 [l,r] 内地月之数个数，那么 g(l,r)=g(1,r)-g(1,l-1) 或 g(l,r)=g(0,r)-g(0,l-1)。那么问题就可以统一成求 g(1,x)。

试填法分析一下，假设目前是 \overline{a_1a_2a_3a_4a_5a_6}（a_1,a_2,a_3 已知），设 (a_1\times 10^5+a_2\times 10^4+a_3\times 10^3)\bmod\sum_a=p，那么只有 (a_4\times 10^2+a_5\times 10+a_6)\bmod\sum_a=\sum_a-p 才能满足条件。

这个题中，模数不是固定的，是随数字的变化而变化，不好 DP，所以直接枚举模数，在本题就是各位数字之和。

也就是说，一些会随着要统计的东西变化而变化的东西，如果不好处理，又不是很大，可以考虑在外层枚举。

枚举模数，或者说数字之和 sum。试填中，记录数字目前填出来的这几位数对 sum 取模的余数 w 和目前地数字和 s（目前填出来的这几位数指的是高位的数，可以理解为后面低位的数都是 0），然后后面要求的未知信息就是，对 sum 取模的余数为 sum-w 且数字之和为 sum-s 的数的个数。

预处理：设 f_{i,j,k,m} 表示 i 位数字，各位数字之和为 j，对 k 取模的余数为 m 的数的个数。

考虑这一位填什么可以推出：

试填：从左往右依次考虑每个数位，仍记录上文中说的 sum,w,s，若第 i 位填 a：

然后试填出答案。

const LL N=90+1;
LL l,r,pw[11],dp[11][N][N][N];

LL get(LL x){
    if(!x) return 0;
    LL tmp=x,sum=0,res;
    vector<LL>num;
    while(tmp){
        num.pb(tmp%10);
        sum+=tmp%10;
        tmp/=10;
    }
    res=(x%sum==0);
    for(LL s=1,sum,now;s<=90;s++){
        sum=s,now=0;
        for(LL i=num.size();i>=1;i--){
            for(LL val=0;val<=min(num[i-1]-1,sum);val++){
                res+=dp[i-1][sum-val][s][(s-(now+val*pw[i-1]%s)%s+s)%s];
            }
            sum-=num[i-1];
            if(sum<0){
                break;
            }
            (now+=num[i-1]*pw[i-1]%s)%=s;
        }
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    pw[0]=1;
    for(LL i=1;i<=10;i++){
        pw[i]=pw[i-1]*10;
    }
    for(LL i=1;i<=90;i++){
        dp[0][0][i][0]=1;
    }
    for(LL i=1;i<=10;i++){
        for(LL j=0;j<=90;j++){
            for(LL k=1;k<=90;k++){
                for(LL m=0;m<k;m++){
                    for(LL val=0;val<=min(9ll,j);val++){
                        dp[i][j][k][m]+=dp[i-1][j-val][k][(m-val*pw[i-1]%k+k)%k];
                    }
                }
            }
        }
    }
    while(cin>>l>>r){
        cout<<get(r)-get(l-1)<<"\n";
    }
    return 0;
}

P6218 [USACO06NOV] Round Numbers S - 洛谷

题面

对于一个数，若其二进制表示下 0 的个数不小于 1 的个数，那么这个数就是圆数。问区间 [l,r] 内有多少个圆数。

题解

分析：二进制下的试填法分析，发现要 DP 的是有 i 位且 0 的个数为 k 的数的个数。但是这里的前导零会影响到 0 的个数，从而影响正确性，所以需要再记录一个 j 表示最高位填什么，试填的时候也要把前导零特殊考虑一下。

预处理：设 f_{i,j,k} 表示二进制下有 i 位，最高位填 j，0 的个数位 k 的数的个数。

试填：要求 [0,x] 之间的圆数个数，分成两种数（x 在二进制下位数为 m）：

1. 二进制位数小于 m；
2. 二进制位数等于 m；

对于第一种数，枚举位数 <m，枚举合法的 0 的数量（或 1 的数量），用 f 求数量。

对于第二种数，从左到右枚举每一位，记录前面 0 的个数，遇到 x 这一位是 1，就枚举后面合法的 0 的个数（或 1 的个数），用 f 求数量。

const LL N=32+5;
LL l,r,dp[N][2][N];

LL get(LL x){
    if(!x) return 1;
    LL tmp=x,res=1;
    vector<LL>a;
    while(tmp){
        a.pb(tmp&1);
        tmp>>=1;
    }
    for(LL i=1;i<a.size();i++){  //数位个数比x小的 
        for(LL j=0;j<=i/2;j++){
            res+=dp[i][1][i-j];
        }
    }
    for(LL i=a.size()-2,cnt=0,val;~i;i--){  //数位个数和x一样的 
        val=a[i];
        if(val){
            for(LL k=0;k<=a.size();k++){
                if(k+cnt>=a.size()-(k+cnt)){
                    res+=dp[i+1][0][k];
                }
            }
        }
        if(!val) cnt++;
        if(!i&&cnt>=a.size()-cnt) res++;
    }
    return res;
}
LL fac[N];
void init(LL n){
    fac[0]=1;
    for(LL i=1;i<=n;i++){
        fac[i]=fac[i-1]*i;
    }
}
LL C(LL n,LL m){
    if(n<m) return 0;
    return fac[n]/fac[n-m]/fac[m];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>l>>r;
    init(31);
    dp[1][0][1]=1,dp[1][1][0]=1;
    for(LL i=2;i<=32;i++){
        for(LL j=0;j<=i;j++){
            if(j) dp[i][0][j]=dp[i-1][0][j-1]+dp[i-1][1][j-1];
            dp[i][1][j]=dp[i-1][0][j]+dp[i-1][1][j];
        }
    }
    cout<<get(r)-get(l-1);
    return 0;
}

1086. 恨7不成妻 - AcWing题库

全场 MVP

题面

对于一个数，如果满足一下任意一种情况，那么它就是一个与 7 相关的数：

• 十进制表示下，数位上有 7；
• 十进制下，数位和是 7 的倍数；
• 这数是 7 的倍数。

求区间 [l,r] 内与 7 无关的数的数位和，T 组数据。

题解

分析：与前几题不一样的是，它求的不是数的数量，而是平方和。

仍然试填法，考虑当第 i 位填 j 时的与 7 无关的数的平方和，假设 i-1 位的数字中与 7 无关的数有 m 个，分别是 A_1,A_2,\dots,A_m。那么第 i 位填 j 的数的平方和就是 \sum_{k=1}^{m}(j\times 10^{i-1}+A_k)^2=m\times(j\times 10^{i-1})^2+2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k)+\sum_{k=1}^{m}A_k^2。

预处理：现在问题就分成了三个子问题 m\times(j\times 10^{i-1})^2、2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k) 和 \sum_{k=1}^{m}A_k^2。

对于第一个子问题 m\times(j\times 10^{i-1})^2，i,j 都是枚举的，唯一要求的就是 m，也就是 i-1 位的数字中与 7 无关的数的数量。所以设 f_{i,j,a,b} 表示有 i 位，最高位填 j，数位和模 7 的余数为 a，数本身模 7 的余数为 b 的数的数量。

设 x=(((a-j)\bmod7)+7)\bmod7 为 i-1 位数的数位和模 7 的余数（i-1 位数的 a），y=(((b-j\times 10^{i-1})\bmod7)+7)\bmod7 为 i-1 位数模 7 的余数（i-1 位数的 b）。那么 m=\sum_{0\le p\le9,p\ne7}f_{i-1,p,x,y}。

推转移式，考虑下一位填什么。

对于第二个子问题 2\times j\times10^{i-1}\times(\sum_{k=1}^{m}A_k)，主要是 \sum_{k=1}^{m}A_k 难求，即 i-1 位的数字中与 7 无关的数的和。所以设 h_{i,j,a,b} 表示有 i 位，最高位填 j，数位和模 7 的余数为 a，数本身模 7 的余数为 b 的数的和。

仍然计算刚才的 x,y。那么 \sum_{k=1}^{m}A_k=\sum_{0\le p\le9,p\ne7}h_{i-1,p,x,y}。

对于满足 h_{i,j,a,b} 条件的 t 个数 B_1,B_2,\dots,B_t，因为最高位填的都是 j，所以 h_{i,j,a,b}=\sum_{k=1}^{t}B_k=\sum_{k=1}^{t}(j\times10^{i-1}+C_k)=t\times j\times10^{i-1}+\sum_{k=1}^{t}C_k，其中 C 是 i-1 位的合法的数（前面计算的 x,y 就是保证它合法的），所以 \sum_{k=1}^{t}C_k=\sum_{0\le p\le9,p\ne7}h_{i-1,p,x,y}。而 t 有是刚才我们求出的 \sum_{0\le p\le9,p\ne7}f_{i-1,p,x,y}。发现都有 \sum_{0\le p\le9,p\ne7} 的一个求和，直接把它提到最前面。

对于第三个子问题 \sum_{k=1}^{m}A_k^2，i-1 位的数字中与 7 无关的数的平方和。设 g_{i,j,a,b} 表示有 i 位，最高位填 j，数位和模 7 的余数为 a，数本身模 7 的余数为 b 的数的平方和。