SRM 510 Div1 Easy TheAlmostLuckyNumbersDivOne

問題

lucky numberとは、4,7のことを言う。
almost lucky numberとは、各桁のうちlucky numberでない数が一つ以下の数のことを言う。

a以上b以下のalmost lucky numberの数を求めよ。

制約条件

a,b ≦ 10^16

方針

almost lucky numberは2^14*15*10(300万以下）通り程度。
というわけで素直に全探索して余裕で間に合うのだが、何故か間に合わないと思いこみDPで解いた。

DP解法は以下の通り。
dp[i][j][k][l][m]にi桁目までで、最後の桁がjで、k=1ならleadingzeroが続いていて、l=1なら今までの数はaよりも小さくなってて、non lucky numberがm個含まれているような数の総数。

これを更新していく。

ソースコード

string s;
int n;
ll dp[20][10][2][2][2]; //pos, last, leadingzero?, smaller?, nonlucky?

ll calc(ll x){
	stringstream ss; ss<<x; s=ss.str();
	n=s.size();
	
	memset(dp,0,sizeof(dp));
	dp[0][0][1][0][0]=1;
	
	rep(i,n)rep(j,10)rep(lz,2)rep(sm,2)rep(lk,2){
		if(sm||j<=s[i]-'0'){
			int nlz=lz, nsm=sm, nlk=lk;
			if(j<s[i]-'0')nsm=1;
			if(j>0)nlz=0;
			if(!nlz&&j!=4&&j!=7)nlk++;
			
			if(nlk<2)rep(k,10){
				dp[i+1][j][nlz][nsm][nlk]+=dp[i][k][lz][sm][lk];
			}
		}
	}
	ll ret=0;
	rep(i,10)rep(sm,2)rep(lk,2)ret+=dp[n][i][0][sm][lk];
	return ret;
}

class TheAlmostLuckyNumbersDivOne {
public:
  long long find(long long a, long long b) {
  	return calc(b)-calc(a-1);
  }
};

追記

dpテーブルに最後の数字を持たせる必要は別になかった。
こんな感じでおｋ

ll dp[20][2][2][2]; //pos, leadingzero?, smaller?, nonlucky?

ll calc(ll x){
	stringstream ss; ss<<x; s=ss.str();
	n=s.size();
	
	memset(dp,0,sizeof(dp));
	dp[0][1][0][0]=1;
	
	rep(i,n)rep(j,10)rep(lz,2)rep(sm,2)rep(lk,2){
		if(sm||j<=s[i]-'0'){
			int nlz=lz, nsm=sm, nlk=lk;
			if(j<s[i]-'0')nsm=1;
			if(j>0)nlz=0;
			if(!nlz&&j!=4&&j!=7)nlk++;
			
			if(nlk<2){
				dp[i+1][nlz][nsm][nlk]+=dp[i][lz][sm][lk];
			}
		}
	}
	ll ret=0;
	rep(sm,2)rep(lk,2)ret+=dp[n][0][sm][lk];
	return ret;
}