#include using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<bool chmax(T &a,const T &b){if(abool chmin(T &a,const T &b){if(b ostream &operator<<(ostream &os,const vector&v){ for(int i=0;i<(int)v.size();i++) os< istream &operator>>(istream &is,vector&v){ for(T &x:v)is>>x; return is; } vector p10{ 1ll, 10ll, 100ll, 1000ll, 10000ll, 100000ll, 1000000ll, 10000000ll, 100000000ll, 1000000000ll, 10000000000ll, 100000000000ll, 1000000000000ll, 10000000000000ll, 100000000000000ll, 1000000000000000ll }; // x, x+1 bool len(ll x){ if(x==1) return 1; ll last=-1; while(x){ last=x%10; x/=10; } return (x%10==1 and last==1); } ll naive(int n){ string p="???"; ll a=0,b=0; for(int i=1;i<=n;i++){ string s=to_string(i); for(int j=0;j+1<(int)s.size();j++){ if(s[j]=='1' and s[j+1]=='2') a++; } if(p.back()=='1' and s[0]=='2'){ // cout<<"! "<>>> dp(m+1,vector>>(2,vector>(2,vector(100,0)))); dp[0][0][0][0]=1; rep(i,m){ int num=s[i]-'0'; rep(j,2){ rep(k,2){ rep(l,80){ rep(p,10){ if(j==0 and p>num) continue; if(k==1 and p==2) dp[i+1][j or p=2) ret++; if(s.size()<=1){ return ret; } int i; for(i=0;i+2<(int)s.size();i++){ ret+=p10[i]; } if(s[0]=='2'){ ll add=0; for(int i=1;i<(int)s.size()-1;i++) add+=10*add+s[i]-'0'; // add++; if(s.back()<'2') add--; ret+=max(0ll,add); return ret; }else if(s[0]<'2') return ret; else return ret+p10[i]; } signed main(){ // ll n;cin>>n; // ll H=solve(n); // cout<>a>>b; ll p=solve(b); ll m=solve(a-1); // cout<