数位dp 不要62

纯纯数位dp板子，可以顺着思路下来。

传统技能学习笔记

不要62 libreoj

设状态为 \(dp[i][j]\) 为第 \(i\) 位是 \(j\) 的可能情况数。

枚举位数，这位的数，低一位的数，将每一位的组合可能存下来，但要把这位是 4 与这位是 6 低一位是 2 的情况排除掉。

void init(){
	dp[0][0]=1;
	for(int i=1;i<=8;i++){
		for(int j=0;j<=9;j++){
			if(j==4){
				continue;
			}
			for(int k=0;k<=9;k++){
				if((j==6&&k==2)){
					continue;
				}
				dp[i][j]+=dp[i-1][k];
			}
		}
	}
}

然后进行计算，将每一位存下来，循环 0-a[i]-1，因为a[i]不能直接取全部情况，注意这时要将这位是2高一位6的情况排除掉，这个可以思考思考就可以了。如果出现哪一位4和62的话直接跳出，因为后面一定就不会取到。

ll dig(int x){
	int cnt=0;
	ll sum=0;
	while(x){
		a[++cnt]=x%10;
		x/=10;
	}
	a[cnt+1]=-1;
	for(int i=cnt;i>=1;i--){
		for(int j=0;j<a[i];j++){
			if(j==2&&a[i+1]==6){
				continue;
			}
			sum+=dp[i][j];
		}
		if(a[i]==4||(a[i+1]==6&&a[i]==2)){
			break;
		}
	}
	return sum;
}

这样计算时要r+1，因为最后一位总是取不到，所以要多打个1就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int n,m;
ll dp[15][15];
int a[15];
void init(){
	dp[0][0]=1;
	for(int i=1;i<=8;i++){
		for(int j=0;j<=9;j++){
			if(j==4){
				continue;
			}
			for(int k=0;k<=9;k++){
				if((j==6&&k==2)){
					continue;
				}
				dp[i][j]+=dp[i-1][k];
			}
		}
	}
}

ll dig(int x){
	int cnt=0;
	ll sum=0;
	while(x){
		a[++cnt]=x%10;
		x/=10;
	}
	a[cnt+1]=-1;
	for(int i=cnt;i>=1;i--){
		for(int j=0;j<a[i];j++){
			if(j==2&&a[i+1]==6){
				continue;
			}
			sum+=dp[i][j];
		}
		if(a[i]==4||(a[i+1]==6&&a[i]==2)){
			break;
		}
	}
	return sum;
}

int main(){
	ios::sync_with_stdio(false);
	init();
	while(1){
		cin>>n>>m;
		if(n==0&&m==0){
			break;
		}
		cout<<dig(m+1)-dig(n)<<"\n";
	}
	return 0;
}