概述

数位dp是一种模式化的dp
一般是从数字的高位到低位进行dp

一般数位dp题目特征都很明显,询问[l,r] 内有多少个数满足某个性质
即求sum[0,r]-sum[0,l-1];

模板

1
2
3
4
5
6
7
8
9
10
11
12
LL dfs(int x,int pre,int ye,int limit)	
{
if(x<0) return ye;
int &ans = d[x][pre][ye];
if(ans!=-1) return ans;
LL res = 0;
int last = limit?dig[x]:9;
for(int i=0;i<=last;++i)
res += dfs(x-1,i,ye || (当前数满足条件),limit && i==last)
if(!limit) ans =res;
return res;
}

表示当前为第x位置,前一位为pre,ye当前数字是否已满足条件,limit表示对当前数位的范围是否有限制
一般用记忆化搜索,d[x][pre][ye],为了避免limit不同时的混淆,只对没有limit时进行记忆化。

二进制数位dp

一般为计数问题,考虑逐位统计

bzoj3209为例

设 $f(x)$ 为 $x$ 的二进制表示中 1 的个数。给定 $n$ ,求 $\prod_{i=1}^nf(i)$

从高位到低位统计,考虑每个1,假设其变为0,则其之后的低位的数可以任取
此时对答案加上所有之后的数取的情况(组合数)
注意最后将n统计进答案

1
2
3
4
5
6
7
8
9
10
11
12
for(int i=tot;i;--i)
{
if(bit[i] == 1)
{
for(int j=(cnt==0);j<i;++j)
res[cnt+j] = (res[cnt+j] + C[i-1][j]);
}
cnt += bit[i];
}
LL ans = cnt;
for(int i=1;i<=tot;++i)
ans = ans*pow_m(i,res[i])%mod;

题目

hdu4352

求LIS长度为K的数
这里有个对LIS的状压技巧,因为LIS最长为10,因此用十位二进制数表示

每次加入一个数字,则去掉比它大的第一个数字,或者说是替换。
因为这样不影响以更大的数结尾的LIS,后加入的数可以直接跟在后面。

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
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int maxn = 22;
LL d[maxn][1<<10][12];
int dig[maxn],K;

inline int get(int x)
{
int cnt = 0;
for(int i=0;i<10;++i) if((1<<i)&x) ++cnt;
return cnt;
}

inline int judge(int st,int i)
{
if((1<<i) & st) return st;
if((1<<i) > st) return st|(1<<i);
st |= 1<<i;
for(int j=i+1;j<10;++j) if((1<<j) & st) return st^(1<<j);
}

LL dfs(int x,int st,int limit)
{
if(x<0) return get(st)==K;
LL &ans = d[x][st][K];
if(!limit && ans != -1) return ans;
int last = limit?dig[x]:9;
LL res = 0;
for(int i=0;i<=last;++i) res+=dfs(x-1,st || i ?judge(st,i):0,limit && (i==last));
if(!limit) ans = res;
return res;
}

inline LL solve(LL n)
{
int len = 0;
while(n)
{
dig[len++] = n%10;
n /= 10;
}
return dfs(len-1,0,1);
}

int main()
{
// freopen("test.txt","r",stdin);
memset(d,-1,sizeof d);
int T;
scanf("%d",&T);
for(int z=1;z<=T;++z)
{
LL L,R;
scanf("%lld %lld %d",&L,&R,&K);
printf("Case #%d: %I64d\n",z,solve(R)-solve(L-1));
}
return 0;
}

hdu3886

求满足区间按照给定关系的上升还是下降的数的个数。
我的定义$d_{x,p,pre}$为当前数位为x,对应关系位置为p,前一个数为pre的所有方案
确定第一个非零的位置后,转移无非有两种,保持当前p,和p+1。
但是这样有可能造成重复的情况比如
– 对于 1111 有 1/111 11/11 111/1 三种划分
/\ 对于 12321 有 12/321 123/21 两种划分
所以我们在满足条件的情况下,优先转移到p+1,比如把上面的状态转移到1/111,12/321。

参考