数位动态规划

概述

数位 DP 的基本思想就是按位 DP,对数字的每一位做 DP。

数位 DP 常用于求解区间内满足条件的数的计数问题。

数位 DP 的一个重要特征是多维度。事实上由于在数位 DP 的过程中有若干限制条件,使得问题的维度较多,因此相比普通 DP 而言,数位 DP 的状态设计就更加凸出了。

考虑到数字大小不超过 N,则其中通常有一个状态表示是否到达数位的上界

因为一个数的长度一般小于等于 30,所以数位 DP 的方程有时会涉及 4,5 个维度,以满足题目给定的要求;也因此,数位 DP 的状态转移相对复杂。区间计数通常使用区间减法,方便计数

[SCOI2009]Windy 数

windy 数:不含前导零且相邻两个数字之差至少为 2 的正整数。求在 A 和 B 之间(包括 A 和 B)有多少个 windy 数?

数位 DP,定义 表示长度为 ,开头数字为 的 windy 数的个数。状态转移方程如下

显然这个方程并没有考虑 A 和 B 的界。为了简化问题,我们考虑求 中 windy 数的个数,再求 中 windy 数的个数,然后相减即可。

于是我们利用 DP 值,对着上界累加出答案。详见 calc() 函数。

#include<cstdio>
#include<cmath>
using namespace std;
const int NL=15;// 数字长度
int f[NL+1][10];
//f[i,j] 长度为 i,开头数字为 j 的 windy 数的个数
void dp_init(){
    for(int i=0;i<=9;i++)f[1][i]=1;
    for(int i=2;i<=NL;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<=9;k++)
                if(abs(j-k)>=2)
                    f[i][j]+=f[i-1][k];

}
int calc(int k){
    int a[NL+1]={0},cnt=0,res=0;
    while(k)a[++cnt]=k%10,k/=10;
    for(int i=1;i<cnt;i++){// 累加所有长度小于 k 的 windy 数
        for(int j=1;j<=9;j++)res+=f[i][j];
    }
    for(int i=1;i<a[cnt];i++)res+=f[cnt][i];// 长度为 k,首位小于 k 的 windy 数
    // 对于长度为 k,开头为 a[cnt] 的 windy 数
    for(int i=cnt-1;i>=1;i--){// 考虑到第 i 位
        for(int j=0;j<a[i];j++){// 开头为 j(未到上界)
            if(abs(a[i+1]-j)>=2)res+=f[i][j];
        }
        if(abs(a[i+1]-a[i])<2)break;
        // 对于到达上界的数,如果上界本身不满足年,就 break
    }// 这个算法不会算到上界本身,所以调用的时候上界要 +1
    return res;
}
int main(){
    int p,q;
    dp_init();
    scanf("%d%d",&p,&q);
    printf("%d",calc(q+1)-calc(p));// 见 calc 中注释
    return 0;
}

[BZOJ3679] 数字之积

f(x) 表示 x 的各位数字之积。给出 n,l,r,求 [l,r) 中满足 的数的个数。

.

f[i,j,k] 表示长度为 i,首位为 j,积为 k 的数的个数(注意,合法的数字中不能有 0 出现)。显然可以得到以下的转移关系

这个方程仍有一个问题,就是 k 的值域。但经过枚举发现,k 的不同值的个数不超过 6000,于是开 map 做一个映射即可。使用 check 函数用来预处理合法的 k。

#include<cstdio>
#include<map>
#define int long long 
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;

int n,L,R,tot;
int f[30][10][6000];

map<int,int> p;
int w[6000];

void check(int a,int b,int c,int d){
    int s=1;
    FOR(i,1,a)s*=2;    if(s>n)return;
    FOR(i,1,b)s*=3;    if(s>n)return;
    FOR(i,1,c)s*=5;    if(s>n)return;
    FOR(i,1,d)s*=7;    if(s>n)return;
    p[s]=++tot, w[tot]=s;
}
void DP(){
    FOR(i,1,9)if(i<=n)f[1][i][p[i]]=1;// 初始化一位数
    FOR(i,1,19) FOR(j,1,9) FOR(k,1,tot) if(f[i][j][k]) FOR(x,1,9)
        if(w[k]*x<=n) f[i+1][x][p[w[k]*x]]+=f[i][j][k];
}
int calc(int m){// 没有取到 m
    int d[30],ld=0,res=0;
    while(m)d[++ld]=m%10,m/=10;// 分解 10 进制位
    for(int i=1,j=ld;i<j;i++,j--)swap(d[i],d[j]);
    FOR(i,1,ld-1) FOR(j,1,9) FOR(k,1,tot) res+=f[i][j][k];// 长度小于 ld
    int pre=1;// 存储之前的位的乘积
    FOR(i,1,ld){FOR(k,1,tot)if(w[k]*pre<=n)FOR(j,1,d[i]-1)res+=f[ld-i+1][j][k];
        pre*=d[i];
        if(pre>n||pre==0)break;
    }
    return res;
}
signed main(){
    scanf("%lld%lld%lld",&n,&L,&R);
    FOR(i,0,29) FOR(j,0,18) FOR(k,0,12) FOR(l,0,10) check(i,j,k,l);
    DP();
    printf("%lld\n",calc(R)-calc(L));
    return 0;
}
/*
 * BUG#1:DP 的时侯 i 的界开成了 [2,19]。应该是 [1,18]
 * BUG#2: 没有统计长度小于 ld 的答案
 * BUG#3:check(i,j,k,l) 写成了 check(i,k,j,l)...
 */

[LG3413] SAC#1 - 萌数

存在长度至少为 2 的回文子串的数是萌的,例如 101,11,110

求 [l,r] 内的萌数。 .

其实只需要考虑连续两位或者三位的数的情况即可。为了方便转移,将首位和次位都纳入 DP 状态中。f[i,j,k] 表示长度为 i,首位为 j,第二位为 k 的萌数个数。转移方程如下

(应该能看懂吧)然后考虑根据上界凑答案。显然我们从高位到低位依此考虑。当前位 i 顶满上界 ,那么枚举下一位(i-1 位)。这时需要考虑枚举的数字与第 i+1 位的关系。如果两者相等,那么构成回文子串,于是后面的随便填。否则用 DP 值累加

注意,不用考虑 j 和 的关系,因为已经纳入状态中。在统计的时侯,如果前面的上界中已经出现回文子串,那么之后的就不需要判断了,直接取所有数即可。最后要注意,这个统计方法是没有考虑上界本身的,因此上界可以特判。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define ROF(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
const int N=1e3+4,P=1e9+7;

int f[N][10][10],m10[N],la;
char a[N];

void DP(){
    FOR(i,0,9) f[2][i][i]=1;
    FOR(i,3,N-1) FOR(j,0,9) FOR(k,0,9){if(j==k)f[i][j][k]=m10[i-2];
        else FOR(x,0,9) f[i][j][k] += j==x?m10[i-3]:f[i-1][k][x];
        f[i][j][k]%=P;
    }
}

int solve(int isleft){// 如果是左区间端点,那么不考虑上界
    scanf("%s",a+1);
    la=strlen(a+1);
    reverse(a+1,a+la+1);
    FOR(i,1,la)a[i]-='0';

    int res=0,fl=0;
    FOR(i,2,la-1) FOR(j,1,9) FOR(k,0,9) res=(res+f[i][j][k])%P;
    FOR(j,1,a[la]-1) FOR(k,0,9) res=(res+f[la][j][k])%P;
    ROF(i,la,2){
        if((i<la&&a[i]==a[i+1])||(i+1<la&&a[i]==a[i+2]))fl=1;
        if(fl)res=(res+a[i-1]*m10[i-2])%P;
        else FOR(j,0,a[i-1]-1)
                res=(res+((i<la&&j==a[i+1])?m10[i-2]:f[i][a[i]][j]))%P;
    }
    if((1<la&&a[1]==a[2])||(2<la&&a[1]==a[3]))fl=1;
    if(!isleft&&fl)res=(res+1)%P;// 即上界也要算进去
    return res;
}

signed main(){
    m10[0]=1;
    FOR(i,1,N-1)m10[i]=m10[i-1]*10%P;
    DP();

    int a=solve(1), b=solve(0);
    printf("%lld\n",(b-a+P)%P);
    return 0;
}
/*
 * BUG#1: 没判断最后一位的回文.L37
 * BUG#2: 没有考虑三位运算符优先级(优先级小于算术加法).L35
 */

[HDU6148]Valley Numer

当一个数字,从左到右依次看过去数字没有出现先递增接着递减的 “山峰” 现象,就被称作 Valley Number。它可以递增,也可以递减,还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。 度度熊想知道不大于 N 的 Valley Number 数有多少。

多组数据, .

为避免分类模糊不清导致计重计漏,将 valley 数分为 4 类:

  1. ,即各位相同的数
  2. 按位非严格单增,但至少有一处是严格增加的
  3. 按位非严格单减,但至少有一处是严格减少的
  4. V 型,至少一处严格减少,至少一处严格增加

状态分别标为 0,1,2,3。设 f[i,j,k] 表示长度为 i,首位为 j,分类为 k 的数的个数。状态转移如下

在最后统计的时侯不要忘了根据上界状态来做合适的贡献处理

#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define ROF(a,b,c) for(int a=b;a>=c;a--)
#define int long long
using namespace std;
const int N=105,P=1e9+7;

int f[N][10][4],ld;
char d[N];

void DP(){
    FOR(i,0,9)f[1][i][0]=1;
    FOR(i,2,N-1) FOR(j,0,9) {f[i][j][0]=f[i-1][j][0];
        FOR(k,0,9) {if(j<=k)f[i][j][1]+=f[i-1][k][1];
            if(j<k)f[i][j][1]+=f[i-1][k][0];
            if(j>=k)f[i][j][2]+=f[i-1][k][2];
            if(j>k)f[i][j][2]+=f[i-1][k][0];
            if(j>=k)f[i][j][3]+=f[i-1][k][3];
            if(j>k)f[i][j][3]+=f[i-1][k][1];
        }
        f[i][j][1]%=P;
        f[i][j][2]%=P;
        f[i][j][3]%=P;
    }
}

void go(){
    scanf("%s",d+1);
    ld=strlen(d+1);
    reverse(d+1,d+ld+1);// 最高位是 ld
    FOR(i,1,ld)d[i]-='0';
    int res=0,sta=0;
    FOR(i,1,ld-1) FOR(j,1,9) FOR(k,0,3) res+=f[i][j][k];// 长度小于 ld
    FOR(j,1,d[ld]-1) FOR(k,0,3) res+=f[ld][j][k];// 长度等于 ld 的情况首位非 0
    res%=P;
    ROF(i,ld-1,1){//sta:0 相同,1 单增,2 单减,3v
        int l=0,r=d[i]-1;
        if(sta==1||sta==3)l=max(l,d[i+1]+0ll);
        FOR(j,l,r) {
            if(sta==0||sta==2){// 相同的贡献
                if(j<=d[i+1])FOR(k,0,3)res+=f[i][j][k];
                else res+=f[i][j][1]+f[i][j][0];
            } else res+=f[i][j][1]+f[i][j][0];
        }
        res%=P;
        if(d[i]<d[i+1]){// 更新状态
            if(sta==1||sta==3){sta=4;break;}// 上界不合法
            else sta=2;
        } else if(d[i]>d[i+1]){if(sta==2||sta==3)sta=3;
            else sta=1;
        }
    }
    if(sta!=4)res++;
    printf("%lld\n",res);
}
signed main(){
    int t;
    DP();
    scanf("%lld",&t);
    while(t--)go();
    return 0;
}
/*
 * BUG#1: L47 少写 f[i][j][0]
 */

[ZJOI2010] 数字计数

给定两个正整数 a 和 b,求在 [a,b] 中的所有整数中,每个数码 (digit) 各出现了多少次。

.

十元组及其运算

数位统计题的优点在于题面简单,暴力好打

首先我们定义一个十元组结构体 表示 的出现次数,那么加减运算就顺便可以定义了

#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
struct data{int c[10];
    data(){FOR(i,0,9)c[i]=0;}// 构造函数
    data(int cnt){FOR(i,0,9)c[i]=cnt;}
    data operator+(data d){// 加法
        FOR(i,0,9)d.c[i]+=c[i];
        return d;
    }
    data operator-(data d){// 减法
        data res=*this;
        FOR(i,0,9)res.c[i]-=d.c[i];
        return res;
    }
    void add(int dig,int cnt){c[dig]+=cnt;}// 增加某一数码的出现次数
    void print(){FOR(i,0,9)printf("%lld",c[i]);}// 输出
};

差分统计

那么首先把区间差分一下,考虑 的出现次数

首先定义 表示以 为首位的 位数的 的出现次数(Data)

显然这个可以直接求,因为后 位不用考虑前导 0 的问题,每个数码的出现次数都为 ,再加上数码 的出现次数 就行:

const int m10[]={1,10,(int)1e2,(int)1e3,(int)1e4,(int)1e5,(int)1e6,(int)1e7,(int)1e8,(int)1e9,(int)1e10,(int)1e11,(int)1e12};
data f(int i,int j){// 首位为 i 的 j 位数中每个数码出现的次数
    int t=j>1?(j-1)*m10[j-2]:0;//j=1 时特判
    data res(t);
    res.add(i,m10[j-1]);
    return res;
}

拆分组合

那么结合上面的统计,对于 位数 ,那么按位统计累加即可

没到达位上限就直接用 函数累加,到达上限了就把上限数码的次数累加,然后考虑下一位就行

#define swap(a,b) (a^=b^=a^=b)
data calc(int n){
    data res;
    int s[20]={0},len=0,sub[20]={0};// 后缀数
    while(n)s[++len]=n%10,n/=10;// 拆位
    for(int i=1;i<=len;i++)sub[i]=sub[i-1]+s[i]*m10[i-1];
    for(int i=1,j=len;i<j;i++,j--)swap(s[i],s[j]),swap(sub[i],sub[j]);// 翻转
    FOR(i,1,9)FOR(j,1,len-1)res=res+f(i,j);// 统计 1~len-1 位数
    FOR(i,1,len){// 首位上限为 s[i],位数为 len-i+1, 对应的 sub_num 为 sub[i+1]
        FOR(k,i==1?1:0,s[i]-1)res=res+f(k,len-i+1);// 第一位是特殊情况
        res.add(s[i],sub[i+1]+1);// 到达上限
    }
    return res;
}

主函数

代码的其他部分

当然要开 longlong

#include<cstdio>
#define int long long 
using namespace std;
int a,b;
signed main(){scanf("%lld%lld",&a,&b);
    (calc(b)-calc(a-1)).print();
    return 0;
}

  转载请注明: Sshwy's Blog 数位动态规划

 上一篇
状态压缩动态规划 状态压缩动态规划
引言状压 DP,是一种动态规划。一般的动态规划状态简单,通常一两个维度就能搞定。不过当状态过于复杂时,简单的维度将无法表示状态,而过多的维度将加大复杂度,于是,就有了状压 DP 的出现。 状态压缩状压 DP 的要点,就是状态压缩。状态压缩
2018.11.16
下一篇 
[HDU2196]Computer [HDU2196]Computer
二次扫描与换根法这种算法通常用于统计无根树上每个结点的答案,并且对于根结点的答案容易统计的题目。这时,我们就把每个结点在 DFS 遍历的同时换作根,同时统计答案。 我们对整棵树做 2 次 dfs: 第一次: 选定一个结点为根(比如 1 号)
2018.11.08
  目录