Submission #1611531

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1000000007

int dp[20][2][2][2];//keta,less?,has4?,has9?
signed main(){
	string a,b;
	cin>>a>>b;
	int n=b.size();
	dp[0][0][0][0]=1;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				for(int l=0;l<2;l++){
					int h;
					if(j)h=9;
					else h=b[i]-'0';
					for(int d=0;d<=h;d++){
						dp[i+1][j||d<h][k||d==4][l||d==9]+=dp[i][j][k][l];
						}
					}
				}
			}
		}
		int ba=0;
		for(int i=0;i<2;i++)ba+=dp[n][i][0][0];
		
		memset(dp,0,sizeof(dp));
		
		int as=stoll(a);
		as--;
		a=to_string(as);
		n=a.size();
		dp[0][0][0][0]=1;
		
		for(int i=0;i<n;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
					for(int l=0;l<2;l++){
						int h;
						if(j)h=9;
						else h=a[i]-'0';
						for(int d=0;d<=h;d++){
							dp[i+1][j||d<h][k||d==4][l||d==9]+=dp[i][j][k][l];
							}
						}
					}
				}
			}
			int aa=0;
			for(int i=0;i<2;i++)aa+=dp[n][i][0][0];
			int B=stoll(b);
			int A=stoll(a);
			cout<<B-A-(ba-aa)<<endl;
	}

Submission Info

Judge Result