AcWing 338. 计数问题（数位DP）

题目链接

https://www.acwing.com/problem/content/340/

思路

我们想要快速求得 [ 1 , n ] [1,n] [1,n]内所有数的某些数字出现的次数，那么我们要从十进制数位出发，我们从左往右或者从右往左枚举每一个数位，对于当前的这个数位我们是已经定了的，所以我们就看当前这个位置的前面和后面分别有多少种枚举的方法，首先无论当前的这一位是否大于我们要计算的位值，我们都会有 ( l − 1 ) × p (l-1) \times p (l−1)×p的方案数量，如果当前计算的位值不为0的话那么说明还有前缀为0的情况，后面我们再加上当当前的这一位和我们要计算的位值相同时，前缀的选法其实已经固定了，我们只需要关注后面的选法，对于我们求的位值小于当前这一位，那么说明后面有从0选到999……种情况，否则只能从0选到后缀的情况，详情请看代码，方便理解

代码

#include
using namespace std;

#define ll long long 

ll get_len(ll x){
	ll l = 0;
	while(x) x/=10,l++;
	return l;
}
ll pow10(ll a,ll b){
	ll ans = 1;
	while(b){
		if(b & 1) ans *= a;
		a *= a;
		b >>= 1;
	}
	return ans;
}

ll count_num(ll n,ll loc){
	int len = get_len(n);
	ll ans = 0;
	for(int i = 1;i  ni时 0种选法
		//loc = ni时 yyy : 0...0 ~ r 即 r + 1 种选法
		//i < dj时 yyy : 0...0 ~ 9...9 即 10^(右边的数的位数) == p 种选法时 
		//yyy : 0...0 ~ 9...9 即 10^(右边的数的位数) == p 种选法
		if(loc >a>>b,a,b){
		if(a>b) swap(a,b);
		for(int i = 0;i