NB群友

一道出题人出的签到题，结果大部分人没签到。
于我而言，是看到数据量很大就慌了，觉得会超时，题面较长也没看下来。

题目链接：https://ac.nowcoder.com/acm/contest/625/A

题意：找出满足$L<=数位积<=R$的数的个数.

思路：问题转换成求$数位积<=R的个数-数位积<=(L-1)的个数$，题解给的是dfs枚举2∼9每个数字出现的次数，然后再组合数统计一下答案，剪剪枝。
题解链接： https://fshp971.com/2019-scut-contest-easy/
题解给的代码:

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxT = 50;
const int P = 1e9+7;
const LL MaxInt = (1LL<<32) - 1;

LL Fac[100], InvFac[100];
LL C[100][100];
int cnt[20];

LL lim;
LL dfs(LL now, int pt) {
    if(pt<=1) {
        int s = 0;
        LL ret = 1;
        REP(i,2,9) {
            s += cnt[i];
            ret = ret * C[s][cnt[i]] % P;
        }
        if(s==0) return 0LL;
        return ret;
    }
    LL ret = 0;
    cnt[pt] = 0;
    while(now <= lim) {
        ret = (ret + dfs(now, pt-1)) % P;
        now *= pt, ++cnt[pt];
    }
    return ret;
}

int main() {
    C[0][0] = 1;
    for(int i = 1; i <= 50; ++i) {
        C[i][0] = C[i][i] = 1;
        for(int k = 1; k < i; ++k) C[i][k] = (C[i-1][k] + C[i-1][k-1]) % P;
    }
    int _; scanf("%d", &_);
    while(_--) {
        LL a,b;
        scanf("%lld%lld", &a, &b);
        lim = b;
        LL sb = dfs(1,9);
        lim = a-1;
        LL sa = dfs(1,9);
        LL ans = (sb - sa + P) % P;
        printf("%lld\n", ans);
    }
    return 0;
}

看到另一篇题解说的是搜索过程枚举每一位数，然后记录一下状态值，剪枝
链接： https://www.cnblogs.com/ymzjj/p/10713187.html

AC的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1e9+7;
int T;
map < ll, ll> mp;
ll L,R;
ll res;
ll dfs(ll x){
    if(mp.count(x)){
        return mp[x];
    }
    ll temp=0;
    for(int i=2;i<=9;i++){
        if(x>=i){
            temp+=dfs(x/i)+1;       //枚举每一位数
        }
    }
    return mp[x]=temp;
}
int main()
{
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&L,&R);
        res=(dfs(R)-dfs(L-1))%M;
        printf("%d\n",res);
    }

    return 0;
}