数位DP笔记

数位DP

1.定义：

数位dp是一种计数用的dp，一般就是要统计一个区间[L,R]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp；

数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位

2.替代

数位DP 都可以通过打表以及记搜来写，但是我搜索写的不好/kk

3.自己做数位DP的一些教训

对于进制拆分的时候边界要注意，看看自己统计答案的时候能不能取到边界
对于前导0的处理，根据是否合法进行处理
结果用到dp出来的值要统计完全，不能遗漏

4.原理……

这个东西大概就是通过数位的拆分，各个数位上的dp值会满足乘法原理这一类的知识然后将各个数位上的dp值统计得出$[1 ~ L-1]$ 的值同理得到$[1 ~ R]$的值，然后利用前缀和的思想$$ans_{L,R} = ans_{1,R} - ans_{1,L-1}$$

得出答案数位DP大部分都是这样一个模板所以说它基本不考，我也不知道为啥学它，它还这么难

5. 例题

1.0 有一说一这个题不该评蓝,这个题比下面那个题简单多了

windy数

简化题意：

输入一个$L$和$R$，求$[L,R]$之间的windy数

windy数：不含前导0的相邻两个数之间差值至少为2

$\exists x,y \in N^+ ,|x-y| \geqslant 2$ 则x,y为windy数

solution：

从总体上看有$ans_{L,R} = ans_{1,R} - ans_{1,L-1}$
然后处理的就有 $[1,L-1]$ 与 $[1,R]$
考虑数位DP，首先考虑每一位上的数对最终答案的贡献，预处理每一位上的贡献设立状态$f_{i,j}$记录第i位上的数位j的贡献$$f_{i,j} += f_{i-1,k} , |j-k| \geqslant 2$$
对答案进行统计即计算[1,L-1]的贡献与[1,R]的贡献

len 表示的为区间右端点的数位长度

a[i]表示第i 位上的数

第一部分对位数小于$len$的数的贡献直接统计 $ans += f_{i,j},j \in[1,9]$
第二部分对最高位但是最高位值小于$a_len$的贡献直接统计 $ans += f_{len,i}$, $i\in$ $[1,a[len])$
第三部分对剩下的$len - 1$位重复进行第二部分的操作只不过最高位变成了第i位

\[\huge ans_{1，x} +=
\begin{Bmatrix} \sum\limits_{i = 1}^{i <len}\sum\limits_{j = 1}^{j \le 9} f_{i,j}\\
\sum\limits_{i = 1}^{i < a[len]}f_{len,i}\\
\sum\limits_{i = 1 } ^ {i < len} \sum\limits_{j = 1} ^ { j < a[i]} f_{i,j}
\end{Bmatrix}
\]

写的好丑/kk

预处理部分

void init(){

	for(ll i = 0 ; i <= 9 ; i++) f[1][i] = 1;

	for(ll i = 2 ; i <= 10 ; i++) {

		for (ll j = 0; j <= 9; j++) {

			for(ll k = 0 ; k <= 9 ; k++)

				if(abs(j - k) >= 2) f[i][j] += f[i-1][k];

//		cout<<f[i][j]<<" ";

		}

//		puts("");

	}

}

第一部分

for(ll i = 1 ; i < len ;i++)

		for(ll j = 1; j <= 9 ;j++)

			ans += f[i][j];

//	cout<<ans<<" ";

第二部分

	for(ll i = 1 ; i < a[len] ; i++)  ans += f[len][i];

//	cout<<ans<<" ";

第三部分

for(ll i = len - 1 ; i >= 1 ;i--){

		for(ll j = 0 ; j < a[i]  ;j++)

			if(abs(j - a[i + 1] ) >= 2) ans += f[i][j];

		if(abs(a[i + 1 ] - a[i]) < 2 ) break;

	}

5.code

#include <iostream>

#include <cstdio>

#include <cmath>

#include <string>

#include <cstring>

#define ll long long

using namespace std;

ll read() {

	ll s = 0, f = 0;

	char ch = getchar();

	while (!isdigit(ch)) f |= ch == '-', ch = getchar();

	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();

	return f ? -s : s;

}

ll f[20][20],a[20];

void init(){

	for(ll i = 0 ; i <= 9 ; i++) f[1][i] = 1;

	for(ll i = 2 ; i <= 10 ; i++) {

		for (ll j = 0; j <= 9; j++) {

			for(ll k = 0 ; k <= 9 ; k++)

				if(abs(j - k) >= 2) f[i][j] += f[i-1][k];

//		cout<<f[i][j]<<" ";

		}

//		puts("");

	}

}

ll ans , len;

ll solve(ll x) {

	memset(a,0,sizeof(a));

	ans = 0 ;

	len = 0;

	while(x){

		a[++len] = x % 10;

		x /= 10;

	}

	for(ll i = 1 ; i < len ;i++)

		for(ll j = 1; j <= 9 ;j++)

			ans += f[i][j];

//	cout<<ans<<" ";

	//处理比len短的部分

	for(ll i = 1 ; i < a[len] ; i++)  ans += f[len][i];

	//处理第 len 位(最高位)

//	cout<<ans<<" ";

	for(ll i = len - 1 ; i >= 1 ;i--){

		for(ll j = 0 ; j < a[i]  ;j++)

			if(abs(j - a[i + 1] ) >= 2) ans += f[i][j];

		if(abs(a[i + 1 ] - a[i]) < 2 ) break;

	}

	//处理非len位的

//	cout<<ans<<" ";

	return ans;

}

int main() {

//	freopen("1.in","r",stdin);

//	freopen("2657.out","w",stdout);

	ll L = read(), R = read();

	init();

	R++;

	cout<<solve(R)-solve(L);

	return 0;

}

2.同样的套路题

只不过$f_{i，j} = \sum f_{i-1,k} , k\in [1,9]$

$f_{i,j}$的含义与上个题一样

转移方程减少了限制但最后的求和满足乘法原理，而且注意取模，因为取模只后相对大小会改变，所以要

答案变成了

\[\huge ans_{1,x} +=
\begin{Bmatrix} \sum\limits_{ i = 1，j = 1}^{i <len,j \leqslant 9} f_{i,j}\\
\sum\limits_{i = 1}^{i < a[len]}f_{len,i}\\
\sum\limits_{i = 1 } ^ {i < len} \times \sum_{j = 1} ^ { j < a[i]} f_{i,j}
\end{Bmatrix}
\]

满足乘法原理,而且注意快速幂取模，LATEX用的不好大概没写错

code

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#define int long long

using namespace std;

const int mod = 1e9 + 7;

inline int read() {

	int s = 0, f = 0;

	char ch = getchar();

	while (!isdigit(ch)) f |= ch == '-', ch = getchar();

	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();

	return f ? -s : s;

}

int L, R, T, len, ans;

int f[20][20],a[20];

int f_pow(int x ,int y){

	int ans = 1 ;

	 while(y) {

	 	if(y & 1) ans = (ans * x) %mod;

	 	x = (x * x) % mod;

	 	y >>= 1;

	 }

	 return ans % mod;

}

void init(){

	memset(f , 0, sizeof(f));

	for(int i = 0 ;i <= 9 ;i++) f[1][i] = i;

		for(int i = 2 ; i <= 18; i++) {

			for(int  j = 0; j <= 9 ;j++) {

				for(int k = 0 ; k <= 9 ;k++)

					f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

				f[i][j] = (f[i][j] + j * f_pow(10, i - 1)) % mod;

				// cout<<"i: "<<i<<" j:"<<j<<" "<< f[i][j] << " ";

		}

		// cout<<"\n";

	}

}

int solve(int x ){

	memset(a, 0, sizeof(a));

	len = ans= 0;

	int sum = 0;

	while(x){

		a[++len] = x % 10;

		x /= 10;

	}

	for(int i = 1 ; i < len ;i++)

		for(int j = 1 ; j <= 9;j++)

			ans = (ans + f[i][j]) % mod;

	//处理比它短的 全都加进去

	for(int i = 1 ; i < a[len] ; i++) ans = (ans + f[len][i]) % mod;

	//处理跟它一样长但是比它第len位小的

	// cout<<ans<<"\n";

	sum += a[len];

	//把第len位的贡献加进去

	for(int i = len - 1 ; i >= 1 ;i-- ){

		for(int j = 0 ; j < a[i] ;j++)

			ans = (ans + f[i][j]) % mod;

		ans = (ans + sum * a[i] * f_pow(10 ,i - 1) % mod)% mod;

		sum += a[i];

	}

	//处理跟它一样长但是小于第 i 位上

	return ans % mod;

}

signed main() {

	T = read();

	init();

	while (T--) {

		L = read(), R = read();

		printf("%lld\n",(solve(R + 1) -solve(L) + mod) %mod);

	}

	return 0;

}

3.小小的变形

这个题小小的不一样，设定状态$f[i][j][k]$表示第$i$ 位上的数(二进制拆分后) 为 $j$，$1$的个数为 $k$

可得转移方程

$
f_{i,1,k} = \sum\limits_{p = 0}^{p \ge 1} \sum_{k = 0}^{k \ge i} f_{i-1,p,k-1}
$

$
f_{i,0,k} = \sum\limits_{p = 0}^{p \ge 1} \sum_{k = 0}^{k \ge i} f_{i-
1,p,k}
$

求解最终答案时，统计一下0的个数和1的个数，分别记录为$cnt1$和$cnt0$得到最终答案：

\[ans_{1,x} +=
\begin{Bmatrix} \ f_{i,0,j}, i\in[1,len),j \in[0,len/2-cnt1] \\
f_{i,1,j},i \in[1,len),j \in[0,i/2]
\end{Bmatrix}
\]

本来想放大一点的，但式子貌似有点长

Code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#define int long long

using namespace std;

int f[40][11][40];

int a[40];

int read() {

	int s = 0, f = 0;

	char ch = getchar();

	while (!isdigit(ch)) f |= ch == '-', ch = getchar();

	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();

	return f ? -s : s;

}

void init(){

	f[1][1][1] = 1 , f[1][0][0] = 1;

	for(int i = 2 ; i < 33 ;i++)

		for(int j = 0 ;j <= 1 ;j++ )

			for(int k = 0 ; k <= i ;k++)

				for(int p = 0 ; p <= 1 ;p++)

					if(!j) f[i][j][k] += f[i-1][p][k];

					else if(k) f[i][j][k] += f[i-1][p][k - 1];

}

int solve(int x){

	memset(a,0,sizeof(a));

	int len = 0;

	while(x) {

		a[++len] = x % 2;

		x /= 2;

	}

	int ans = 0,cnt1= 1 , cnt0 = 0;

	for(int i = len - 1; i >= 1 ;i--) {

		int x = a[i];

		if(x) {

			for(int j = 0 ; j <= len / 2 - cnt1 ;j++) {

				ans += f[i][0][j];

			}

		}

		cnt1 += x;

		cnt0 += (x == 0);

		if(cnt0 >= cnt1 && i == 1) ans++;

	}

	for(int i = 1 ; i < len ;i++)

		for(int j = 0 ; j <= i/2 ;j++)

			ans += f[i][1][j];

	return ans;

}

signed main(){

	init();

	int L = read() , R = read();

	cout<<solve(R) - solve(L-1);

	return 0;

}

感觉自己数位DP还是没学好

巴特西