#include<bits/stdc++.h>
using namespace std;
long long dp[22][12][12][2],dig[22];
bool kc[22][12][12][2];
long long f(int n,int a,int b,bool ck,bool st)
{
if(n<0) return 1;
if(ck)
{
long long ans=0;
for(int j=0;j<=dig[n];j++)
{
if(!st&&j==0) ans+=f(n-1,a,b,ck&(j==dig[n]),false);
else if(j!=a&&j!=b) ans+=f(n-1,b,j,ck&(j==dig[n]),true);
}
return ans;
}
else
{
if(kc[n][a][b][st]) return dp[n][a][b][st];
kc[n][a][b][st]=true;
long long ans=0;
for(int j=0;j<=9;j++)
{
if(!st&&j==0) ans+=f(n-1,a,b,false,false);
else if(j!=a&&j!=b) ans+=f(n-1,b,j,false,true);
}
return dp[n][a][b][st]=ans;
}
}
long long solve(long long val)
{
if(val==0) return 0;
int cnt=0;
while(val) dig[cnt++]=val%10,val/=10;
return f(cnt-1,11,10,true,false);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long l,r;
cin>>l>>r;
cout<<solve(r)-solve(l-1);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |