SRM510 Div1 Easy - TheAlmostLuckyNumbersDivOne

問題

4/7以外の数字を0個か1個含む数をAlmostLuckyNumberと呼ぶ
区間[a,b]にそんな数が何個あるか求める

解法

一瞬で「これは桁dpしかねえ!!」ってなって考えることをやめたんだけどワンチャン全列挙の方が楽?

実装

dp[i][j][k][L]
i: i桁目まで確定してる
j: 4/7以外の数字を既に使ったかどうか
k: nより小さいことが確定してるかどうか
L: 0以外の数字を既に使ったかどうか
↑これを忘れるとleading zeroとそうじゃない0の区別がつかなくて状態jがめちゃくちゃになる(なった)

わかりやすさのためjで場合分けした
j=1ならもう4か7しか採用できない その2通りを手書きした
j=0ならその制約がまだないからlim以下の数字は何でも採用できる

class TheAlmostLuckyNumbersDivOne {
	public:
	ll dig(ll n) {
		string s = to_string(n);
		ll dp[20][2][2][2] = {};
		dp[0][0][0][0] = 1;
		rep(i,s.size()) rep(j,2) rep(k,2) rep(l,2) if (dp[i][j][k][l]) {
			if (j) {
				if (k || '4'<=s[i]) dp[i+1][j][k|('4'<s[i])][1] += dp[i][j][k][l];
				if (k || '7'<=s[i]) dp[i+1][j][k|('7'<s[i])][1] += dp[i][j][k][l];
			}
			else {
				int lim = (k ? 9 : s[i]-'0');
				rep(d,lim+1) dp[i+1][((!l && d!=0) || l) && d!=4 && d!=7][k|(d<lim)][l|(d!=0)] += dp[i][j][k][l];
			}
		}
		return dp[s.size()][0][0][1] + dp[s.size()][0][1][1] + dp[s.size()][1][0][1] + dp[s.size()][1][1][1];
	}
	
	ll find(ll a, ll b) {
		return dig(b) - dig(a-1);
	}
};