数位DP

数位DP

十二月 01, 2021

数位DP

数位DP问题关键：

一般会问某一个区间里面满足某种性质的数的个数

技巧一：

$[x,y]$ = $f(y)-f(x-1)$ 类似前缀和的方式

技巧二：

以树的方式思考DP方式

例题（持续更新）：

度的数量

题目描述：求给定区间 $[X,Y]$ 中满足下列条件的整数个数：这个数恰好等于 $K$ 个互不相等的 $B$ 的整数次幂之和。

数据范围：$x,y\le 2^{31}-1,k\le 20$

首先我们要把N拆成B进制数

$N=\overline{a_{n-1}~a_{n-2}~a_{n-3}\dots a_0}$

  1. 最高位填 $0\sim a_{n-1}-1$ ，显然这里后面的几位在 $0\sim B-1$ 之间可以随便填

    如果当前位是1，那么我们有 $\binom B {k-1}$ 种填法

    如果不是1，那么我们有 $\binom B k$ 种填法，总方案数就是两者相加

  2. 最高位填$a_{n-1}$ ，我们的下一位可以怎么填呢？

    显然我们后面的一位是只能在 $0\sim a_{n-2}$ 里面填，这时我们可以继续按方案一继续讨论，知道填到 $a_0$ 为止

当然，我们也可以直接用记忆化搜索来解决，就没有这么麻烦了，只需要考虑转移方程，然后写记忆化搜索即可~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<bitset>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int mod=1e9+7;
const int N=20;
typedef pair<int,int> P;

namespace Edge{
    struct edge{
        int to,nxt,val;
    }e[N];

    int head[N],cnt;

    inline void add(int u,int v,int w){
        e[++cnt].val=w;
        e[cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
    }
}
namespace scan{
    template <typename T>
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template <typename T>
    void write(T x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
using namespace Edge;

int T,f[N<<1][N<<1],C[N][N];
int l,r,k,b;
int a[N];

int dfs(int pos,int pre,int limit){//pos是枚举到哪一位，pre是目前已经有几个1了，limit是当前是否最高位的最大数
    if(pre>k){
        if(!limit) f[pos][pre]=0;
        return 0;
    }
    if(!pos) return pre==k;
    if(!limit && f[pos][pre]!=-1) return f[pos][pre];
    int up=limit ? a[pos] : b-1;
    int res=0;
    for(int i=0;i<=min(up,1);i++){
        res+=dfs(pos-1,pre+(i==1),limit && i==up);
    }
    if(!limit) f[pos][pre]=res;
    return res;
}

inline int dp(int n){
    if(!n) return 0;
    int pos=0;
    while(n){
        a[++pos]=n%b;
        n/=b;
    }
    return dfs(pos,0,1);
}
int main(){
    memset(f,-1,sizeof(f));
    read(l),read(r);
    read(k),read(b);
    write(dp(r)-dp(l-1),'\n');
    return 0;
}

数字计数

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

数据范围：$1\le a ,b\le10^{18}$

暴力的做法很显然了，而且这个题意和数据范围一看就很数位DP

所以我们直接考虑方程：$f_{i,j}$ 表示枚举到第 $i$ 位，已经选了 $j$ 个 $d$ 的方案数，其中 $d$ 是我们当前枚举的那个数

那么我们的转移也很显然：

这个题我们在做的时候要有一个细节：如果我们枚举的这个数当前位是最高位且为0的话，这一位应该是没有贡献的，所以我们应该记忆化搜索时多加一个变量zero来限制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<cctype>
#include<bitset>
#include<vector>
#include<map>
#include<set>
#define int long long
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
const double pi=3.141592653589793;
typedef long long ll;
typedef pair<int,int> P;

namespace Edge{
    struct edge{
        int to,nxt,val;
    }e[N];

    int head[N],cnt;

    inline void add(int u,int v,int w){
        e[++cnt].val=w;
        e[cnt].to=v;
        e[cnt].nxt=head[u];
        head[u]=cnt;
    }
}
namespace scan{
    template <typename T>
    void read(T &x){
        x=0; char c=getchar(); int f=0;
        for(; !isdigit(c); c=getchar()) f |= c=='-';
        for(; isdigit(c); c=getchar()) x = x*10+(c^48);
        if(f) x = -x;
    }

    template <typename T>
    void write(T x,char ch){
        if(x<0) putchar('-'), x = -x;
        static short st[30],tp;
        do st[++tp] = x%10, x/=10; while(x);
        while(tp) putchar(st[tp--] | 48);
        putchar(ch);
    }
}
using namespace scan;
using namespace Edge;
int n,m,now;
int a[N];
int f[1000][1000];//f[i][j] 表示第i位上的数有j个k时，可能的方案数
inline int dfs(int pos,int now,int res,int limit,int zero){//zero是本题的点睛之笔
	if(!pos) return res;
	if(!limit && !zero && f[pos][res]>=0) return f[pos][res];
	int up=limit ? a[pos] : 9;
	int ans=0;
	for(int i=0;i<=up;i++) 
		if(zero && (i==0)) ans+=dfs(pos-1,now,res,limit && (i==a[pos]),1);
		else ans+=dfs(pos-1,now,res+(i==now),limit && (i==a[pos]),0);
	if(!limit && !zero) f[pos][res]=ans;
	return ans;
}
inline int dp(int q,int n){
	int pos=0;
	while(n){
		a[++pos]=n%10;
		n/=10;
	}
	return dfs(pos,q,0,1,1);
}
signed main(){
	memset(f,-1,sizeof(f));
    read(n),read(m);
    for(int i=0;i<=9;i++) write(dp(i,m)-dp(i,n-1),' ');
    return 0;
}

烦人的数学作业

题目简化：给你 $T$ 对数，每对数里有两个数 $l,r$ ，让我们求出 $[l,r]$ 里面每个数各位相加之和，答案对$1e9+7$ 取模

$T\le 20~~1\le x,y\le 10^{18}$

这个题嘛，我们完全可以像上个题一样，先求出各个数出现的次数，然后乘一下那个数是多少就行了，不放代码了（

数页码

题目描述：请你求出全部页码中所有单个数字的和

$1\le n \le 10^9$

这显然还不如上个题难（，下一个吧