Background

Special for beginners, ^_^

Description

查圈圈

Format

Input

\(T\in[1,1000]\)
\(a,b\in[1,10^{14}]\)

Output

每组数据一个结果

Sample 1

Input

11
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
1 100

Output

0
0
0
1
0
1
0
2
1
1
111

Limitation

1s, 1024KiB for each test case.

Hint

#pragma comment(linker, "/STACK:102400000000,102400000000")
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 1e5+8;
/****************************************************/

LL a,b;
    //   0 1 2 3 4 5 6 7 8 9
int h[]={1,0,0,0,1,0,1,0,2,1};
void bruteforce(){
    LL sum = 0;
    for(LL i = a;i<=b;i++){
        LL tem = i;
        while(tem) sum+=h[tem%10],tem/=10;
    }
    printf("%lld\n",sum);
}

int len ,num[20];
LL dp[20][12][40];

LL dfs(int pos,int fir,bool limit,bool zero,int sum){
    if(pos<0) return sum;

    LL &d = dp[pos][fir][sum];
    if(!limit && d!=-1) return d;
    int endi = 9;if(limit) endi = num[pos];
    LL res = 0;
    for(int i=0;i<=endi;i++){
        if(zero){
            if(i == 0)
                res += dfs(pos-1,10,limit&&i==endi,1,0);
            else
                res += dfs(pos-1, i,limit&&i==endi,0,h[i]);
        }
        else {
            res += dfs(pos-1,fir,limit&&i==endi,0,sum+h[i]);
        }
    }

    if(!limit) d = res;
    return res;
}

LL solve(LL n){
    len = 0;
    while(n){
        num[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,10,1,1,0);
}

int main(){
    memset(dp,-1,sizeof(dp));
    int _ = 1;
    for(scanf("%d",&_);_--;){
        scanf("%lld%lld",&a,&b);

//        bruteforce();
        printf("%lld\n",solve(b)-solve(a-1));
    }
    return 0;
}

Source

tabris