数位DP,到每个position时,都可以从这个position开始,也可以继承前面的数。
#include <bits/stdc++.h>
using namespace std;
#define File(x) freopen("(x)","r",stdin)
#define pf printf
#define ull unsigned long long
#define db double
#define ll long long
#define MAXN
#define MAXM
#define P
ll dp[21][2][2][2][2];
int a[21];
int len;
ll dfs(int pos,int ans,int has0,int has1,int has2,int lead,int limit){
if(!pos)return ans;
if(dp[pos][ans][has0][has1][has2]!=-1&&!lead&&!limit)
return dp[pos][ans][has0][has1][has2];
ll re=0;
int up=limit?a[pos]:9;
for(int i=0;i<=up;i++){
int d0=0,d1=0,d2=0,dans=0;
if(i%3==0)d0=1;
else if(i%3==1)d1=1;
else d2=1;
if(has1){
if((i+1)%3==0)d0=1;
else if((i+1)%3==1)d1=1;
else d2=1;
}
if(has2){
if((i+2)%3==0)d0=1;
else if((i+2)%3==1)d1=1;
else d2=1;
}
if(d0&&(!lead||lead&&i))dans=1;
re+=dfs(pos-1,ans||dans,d0,d1,d2,!i&&lead,limit&&i==up);
}
if(!lead&&!limit)dp[pos][ans][has0][has1][has2]=re;
// cout<<has0<<" "<<has1<<" "<<has2<<endl;
return re;
}
ll calc(ll x){
len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
memset(dp,-1,sizeof(dp));
return dfs(len,0,1,0,0,1,1);
}
int main(){
int T;
cin>>T;
while (T--)
{
ll l,r;
cin>>l>>r;
cout<<calc(r)-calc(l-1)<<endl;
}
return 0;
}
F Find 3-friendly Integers