数位DP

P2602 数字计数

给定正整数a,b,求 $[a, b]$ 所有的整数中,0到9每个数码各自总共出现多少次

由前缀和的思想,设 $s u m [n]$ 表示 $[0, n]$ 中0到9各个数码各自出现了多少次

那么 $s u m [b] - s u m [a - 1]$ 就是所求值

问题转化为如何求 $s u m [n]$ 即 $[0, n]$ 中0到9各个数码各自出现了多少次

设计状态 $d p [i]$ 表示"当范围涵盖了完整的i位时,前i位中每个数字出现的次数."

啥意思呢?

比如对于 $[1000, 1999]$ 显然能够找出i=1的完整区间,比如 $[1000, 1009]$ 等等

显然也能够找出i=2的完整区间,比如 $[1900, 1999]$ 等等

显然也能够找出i=3的完整区间,比如 $[1000, 1999]$ ,只有这一个

找不出i=4的完整区间了

如果对于[10,2000000],这就可以找到i=4的完整区间,也就是低四位能够遍历[0,9999]这个范围的区间,比如

$[10000, 19999]$

这样设计dp有一个隐患就是,忽略了前导0的区别.比如给定区间[0,999],显然最大可以找到i=3的区间[0,999]

但是正常情况下,0不能作为前导,也就是说不能有012或001或000或020这种数字,可以有210或100这种数字

最后再考虑去除前导零的情况,现在先不考虑

状态转移方程为: $d p [i] = 10 \times d p [i - 1] + 10^{i - 1}$ 如何考虑这个方程呢?排列组合问题

第i位假设放了一个X(先不管到底放了啥),考虑他对低i-1位的影响,

X有0,1,2,...,9十种可能,于是之前计算得到的dp[i-1]就得乘以10,

也就是说,1在低i-1上出现过 $10 \times d p [i - 1]$ 次

okk,现在看低i-1位给第i位造成的影响,第i位假如放一个1,低i-1位随便放有 $10^{i - 1}$ 种放法

因此1就在第i位上出现过 $10^{i - 1}$ 次

举个实际例子,以[0,999]为例,前导零的情况也计算在内

$d p [1] = 1$ ,边界条件,意思是区间为[0,9]的时候,一个数字显然只出现一次

$d p [2] = 10 \times d p [1] + 10^{1} = 20$

假设个位上放一个X,十位有十种可能,0X,1X,2X,3X,...,9X,也就是说,十位对个位计数的贡献就是 $10 \times d p [1]$

假设十位上放一个X,个位有十种可能,X0,X1,X2,X3,...,X9.也就是说,个位对十位计数的贡献就是 $10^{1}$

笑死,只有两位,要不你影响我,要不我影响你,怎么贡献方式还不一样?

再多一位就可以体现了

$d p [3] = 10 \times d p [2] + 10^{2} = 300$

这时候发现貌似不容易计算百位对于前两位的贡献了,如何解释 $10 \times d p [2]$ 怎么来的呢?

可以这样想:

原来在计算 $d p [2]$ 时,这样只有一个[0,99]区间,而考虑了百位之后,就有

$[0, 99], [100, 199], [200, 299], . . ., [900, 999]$ 这10个区间了,每个区间内数字的出现个数都是 $d p [2]$ 现在有十个相同区间,因此当有三位的时候,从前两位计算得到的数字出现个数就是 $10 \times d p [2]$

假设百位上放一个X,前两位稍微一动就是一个新数,X就得多记录一次

比如X23,X24,X25,这样百位上的X就记了3次.那么前两位一共有多少种可能的排列呢? $10^{2}$ 那么X在第三位上出现的次数就是 $10^{2}$

然后考虑如何去除前导0

去除前导零,也就是给0的计数中去掉0出现在最高位的情况

去除前导0,只会对0的计数有影响,对其他数字没有影响,因为

012345去除前导0不是说把012345给去掉,而是保留12345,12345这五个数字各自统计一次,0此时不应计数

要去除i=6上的前导零计数,也就是去除

0XXXXX这种情况对0计数的贡献,显然有 $10^{5}$ 种

去除i=5上的前导零计数,也就是去除

0XXXX这种情况对0计数的贡献,显然有 $10^{4}$ 种

也就是去除第i位上的前导0影响,就是去除 $10^{i - 1}$ 次0的计数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=15;
long long dp[maxn];
long long pow_10[maxn];

vector<long long> solve(long long n){
    long long temp=n;
    int length=0;
    int top[maxn];
    vector<long long> result(10);
    while(n){
        top[++length]=n%10;
        n/=10;
    }
    for(int i=length;i>=1;--i){
        for(int j=0;j<10;++j){
            result[j]+=dp[i-1]*top[i];
        }
        for(int j=0;j<top[i];++j){
            result[j]+=pow_10[i-1];
        }
        temp-=pow_10[i-1]*top[i];
        result[top[i]]+=temp+1;
        result[0]-=pow_10[i-1];
    }
    return result;
}
long long l,r;
int main(){
    cin>>l>>r;
    pow_10[0]=1;
    for(int i=1;i<maxn;++i){
        dp[i]=dp[i-1]*10+pow_10[i-1];
        pow_10[i]=10*pow_10[i-1];
    }
    vector<long long>left=solve(l-1);
    vector<long long>right=solve(r);
    for(int i=0;i<=9;++i){
        cout<<right[i]-left[i]<<" ";
    }
    return 0;
}

其中比较抽象的是后面这个循环,他里面都干了什么呢?

for(auto j=0;j<10;++j)result[j]+=dp[i-1]*top[i];

计算当前位i随便安排时,对前i位中,数位统计的贡献

使用 $t o p [i]$ 因为第i位上只有 $[0, t o p [i] - 1]$ 共 $t o p [i]$ 种情况

为什么不是 $[0, t o p [i]]$ 共 $t o p [i] + 1$ 种情况?假如对于 $[0, 6524]$

当前i=4,top[4]=6,可以找到区间[0,999],[1000,1999]

[2000,2999],[3000,3999],[4000,4999],[5000,5999]

共6个=top[4]

没有包括[6000,6999],因为最大到6524,即top[i]作为最高位时前i位找不出完整的区间来

for(auto j=0;j<top[i];++j)result[j]+=pow(10,i-1); 

计算前i位随便安排时,对第i位数位统计的贡献

由于最高位上只可能出现 $[0, t o p [i] - 1]$ ,再高top[i]没有完全区间,再高 $t o p [i] + 1$ 不可能出现,因此不能统计对 $[t o p [i], 9]$ 这些数字的贡献

比如当n=6524

i=6,也就是说存在1XXX,2XXX,3XXX,4XXX,5XXX这些完整区间(XXX表示[0,999])

6XXX没有完全区间,只有[6000,6524]

更不存在7XXX了

       
temp-=pow(10,i-1)*top[i];//去掉最高位
result[top[i]]+=temp+1;//之前统计贡献时,i位的最高数字总是不满区间,现在单独处理

啥意思呢?还是n=6524举例子

temp=n=6524

然后temp=6524-6000=524

这524就是对top[4]=6统计次数的贡献,也就是6在i=4位上出现了524+1=525次

加一的原因是,524表示[0,524]共525种情况

result[0]-=pow(10,i-1);//去除前导零

前导零有多种情况,比如0524,0024,0004,0000

这里每次只会处理一种情况,i=4时只会消除0999,0998,...,0000这种前导0.

P8764 二进位问题

$[1, n]$ 这些整数中,二进制表示有k个1的有多少个

如果问题变成:m个二进制位,其中有k个1的有多少个数

显然是 $C_{m}^{k}$

假设n表示成二进制形式之后,最高位是 $b i t [l e n] = 1$ ,最低位是 $b i t [1]$

显然前 $l e n - 1$ 位所有状态都包含在内了,因此首先有 $C_{l e n - 1}^{k}$ ,也就是最高位位0时,低 $l e n - 1$ 位任意安排

下面考虑最高位为1的情况,

从次高位 $b i t [l e n - 1]$ 往低位bit[1]方向看

如果 $b i t [i]$ 为0则跳过,否则加上 $C_{i - 1}^{k - t}$

其中t表示 $[i + 1, l e n]$ 这些位上的1个数

比如 $n = 101000, l e n = 6$

i	bit[i]	操作
5	0	跳过
4	1	$+ C_{4 - 1}^{k - 1}$

为啥加上这个数呢?第4位上有一个1,这表明存在

$[100000 b, 100111 b]$ ,低三位存在完整区间,从这个完整区间中统计有 $k - 1$ 个1的数,是因为之前已经有一个1了,需要在剩下的位中找出k-1个1即可

现在的主要问题是如何快速求解 $C_{m}^{k}$

$C_{m}^{0} = 1$

$C_{m}^{k} = C_{m - 1}^{k - 1} + C_{m - 1}^{k}$

用 $c [m] [k]$ 数组预处理即可

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//c[m][k]
const int maxm=100;
const int maxk=100;
long long c[maxm][maxk];


void init(){
    // c[1][0]=c[1][1]=1;
    c[0][0]=1;
    for(int i=1;i<maxm;i++){
        c[i][0]=1;
        for(int j=1;j<i;++j){
            c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
        c[i][i]=1;
    }
}
void print(){
    for(int i=1;i<20;i++){
        for(int j=0;j<=i;j++){
            cout<<c[i][j]<<" ";
        }
        cout<<endl;
    }
}

long long n;
int k;
long long bit[maxm];
long long len;

int main(){
    init();
    cin>>n>>k;
    long long temp=n;
    while(temp){
        bit[++len]=temp&1;
        temp>>=1;
    }
    long long result=0;
    result+=c[len-1][k];
    int t=1;
    for(int i=len-1;i>=1;--i){
        if(bit[i]==0){
            continue;
        }
        if(k-t<0)break;
        result+=c[i-1][k-t];
        ++t;

    }
    cout<<result<<endl;

    return 0;
}

P2657 windy数

定义windy数:相邻两个十进制位必须至少差2,比如135,2597等等

给定区间[l,r]求这之间的windy数有多少

问题转化为[1,n]中的windy数有多少

设计状态: $d p [i] [j] 表示 i 个 10 进制位, 最高位第 i 位上是 j 的 w i n d y 数的个数$ 边界条件显然是只有一位的时候, $d p [1] [j] = 1$

转移方程: $d p [i] [j] = \sum_{| k - j | \geq 2} d p [i - 1] [k]$

下面考虑[1,n]中有多少windy数

首先划分成十进位

dec[len],dec[len-1],...,dec[1],最高位是dec[len]

那么显然有低len-1位的完整区间,全算上

第len位上,从1到dec[len]-1这些dp[len][i]也是都有的

只剩下len位上放dec[len]的情况了,这是最贴近上边界的情况,如何考虑?

i从len-1往1遍历

对于当前位i,尝试放置 $0 \leq j < d e c [i]$ ,因为第i位最高可以为dec[i],比他小的数都存在

然后判断j是否合法,依据就是j和dec[i+1]距离是否大于等于2,

如果是,则加上 $d p [i] [j]$

这样第i位就统计完毕,尝试往更低位统计,第i位最终放置的是dec[i]

如果dec[i+1]和dec[i]相差小于2,就不能继续往低位统计了

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=20;
long long dp[maxn][10];
void init(){
    for(int j=0;j<10;++j){
        dp[1][j]=1;
    }
    for(int i=2;i<maxn;i++){
        for(int j=0;j<10;++j){
            for(int k=0;k<10;k++){
                if(abs(j-k)>=2){
                    dp[i][j]+=dp[i-1][k];
                }
            }
        }
    }
}
long long solve(int n){
    if(n==0){
        return 0;
    }
    long long result=0;
    long long temp=n;
    long long dec[maxn];
    memset(dec,0,sizeof(dec));
    int len=0;
    while(temp){
        dec[++len]=temp%10;
        temp/=10;
    }
    // cout<<"actived"<<endl;
    for(int i=1;i<=len-1;++i){
        for(int j=1;j<=9;++j){
            result+=dp[i][j];
        }
    }
    for(int j=1;j<dec[len];++j){
        result+=dp[len][j];
    }
    for(int i=len-1;i>=1;--i){
        // cout<<"in loop"<<endl;
        for(int j=0;j<=dec[i]-1;++j){
            if(abs(j-dec[i+1])>=2){
                result+=dp[i][j];
            }
        }
        if(abs(dec[i]-dec[i+1])<2){
            break;
        }
    }



    return result;
}


int l,r;

int main(){
    cin>>l>>r;
    init();
    // cout<<solve(r+1)<<endl<<solve(l)<<endl;
    cout<<solve(r)-solve(l-1)<<endl;


    return 0;
}

P4999 烦人的数学作业

给定区间[l,r],求每个数各个十进制位的数字和

比如[123,125],就有1+2+3+1+2+4+1+2+5

首先问题转化为[1,n]区间上拆分数字和P1836 数页码

然后问题还可以转化为P2602求每个数字出现的次数

最终累计i×i的出现次数即可

dustland

动态规划-数位DP

数位DP

P2602 数字计数

P8764 二进位问题

P2657 windy数

P4999 烦人的数学作业