#include #include using namespace std; using i64 = int64_t; int cmp(int x, int y) { if(x < y) { return 0; } if(x == y) { return 1; } return 2; } // [1, x] の範囲において、数字を繋げて書くというのを無視した上で '12' が現れる個数 i64 g1(i64 x) { string s = to_string(x); int n = static_cast(s.size()); // dp[未満/丁度/超過][ひとつ右の数字が2だったか]['12'の個数] := パターン数 vector>> dp(3, vector>(2, vector(n, 0))); dp[1][0][0] = 1; for(int i=n-1; i>=0; --i) { vector>> ndp(3, vector>(2, vector(n, 0))); for(int flag=0; flag<3; ++flag) { for(int was2=0; was2<2; ++was2) { for(int cnt12=0; cnt12(s.size()); // dp[未満/丁度/超過][末尾の数字][先頭の数字] := パターン数 vector>> dp(3, vector>(11, vector(10, 0))); dp[1][10][0] = 1; for(int i=n-1; i>=0; --i) { vector>> ndp(3, vector>(11, vector(10, 0))); for(int flag=0; flag<3; ++flag) { for(int trail=0; trail<11; ++trail) { for(int lead=0; lead<10; ++lead) { if(!dp[flag][trail][lead]) { continue; } for(int d=0; d<10; ++d) { int nflag = cmp(d, s[i]-'0'); if(nflag == 1) { nflag = flag; } int ntrail = trail == 10 ? d : trail; int nlead = d == 0 ? lead : d; ndp[nflag][ntrail][nlead] += dp[flag][trail][lead]; } } } } dp = ndp; } i64 res = 0; for(int flag=0; flag<2; ++flag) { res += dp[flag][2][2]; } return res; } i64 f(i64 x) { return g1(x) + g2(x); } int main(void) { i64 a, b; scanf("%ld%ld", &a, &b); i64 res = f(b) - f(a-1); string sa = to_string(a); if(sa[0] == '2' && sa.back() == '2') { --res; } printf("%ld\n", res); return 0; }