2019华工校赛 A.NB群友

https://ac.nowcoder.com/acm/contest/625/A

题意：求每位数字为 $2-9$2−9且满足 $每位数字相乘在区间[l,r]$每位数字相乘在区间[l,r]的数字个数。
思路：在比赛时没有做出来十分可惜。出现了以下几个问题：
$1.$1.这道题的范围是 $2^{32}$232，而非常见的 $2^{31}$231,比赛时开了 $ll$ll，以为两个 $int$int相乘不会溢出，但是 $2^{32}\ast 2^{32}=2^{64}$232∗232=264,应该开 $ull$ull才行。
$2.$2.效率问题，可以直接一次 $dfs$dfs找遍位于 $[l,r]$[l,r]的满足要求的个数，而我却用了 $dfs\left(r\right)-dfs(l-1)$dfs(r)−dfs(l−1)，如果 $l$l和 $r$r是较大但接近的两个数，效率差距是比较大的。比赛时觉得判断大于 $r$r剪枝很方便，但是小于 $l$l不太好判断如何剪枝，但实际上最后找完2~9之后判一下就好了。
$3.$3.比赛时回想到之前做过的一道拼木棍的爆搜题，误认为从9到2搜索要比从2到9搜索高效，因为先大后小可以更快的回溯，剪掉一颗大子树，这其实是有问题的。那道题的特点是“小的比较灵活，先小后大很多集中在递归较深时才回溯，而先大后小，很快就会发现不合法，回溯”，而这道题是要所有满足的个数，小的和大的没有什么优先不优先的特点，搜的方向对效率是没有影响的。

下面是修改后的代码：560ms

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define mod 1000000007 
 
ll t,l,r;
ll cnt[10];
ll fac[50],inv[50];
 
ll pow_mod(ll a,ll n)
{
    if(n==0)return 1;
    ll x=pow_mod(a,n/2);
    x=x*x%mod;
    if(n&1)x=x*a%mod;
    return x; 
}
 
ll dfs(int cur,ll mul)
{
    if(cur==10)
    {
        if(mul<l||mul==1)return 0;
        ll sum=0;
        for(int i=2;i<=9;i++)sum+=cnt[i];
        ll ret=fac[sum]; 
        for(int i=2;i<=9;i++)ret*=inv[cnt[i]],ret%=mod;
        return ret;
    }
    else
    {
        ll ans=0;
        for(int i=0;mul<=r;i++,mul*=cur)
        {
            cnt[cur]=i;
            ans+=dfs(cur+1,mul);
            ans%=mod;
        }
        return ans;
    }
}
 
int main()
{
  // freopen("input.in","r",stdin);
    fac[0]=inv[0]=1;
    for(int i=1;i<50;i++)fac[i]=fac[i-1]*i%mod,inv[i]=pow_mod(fac[i],mod-2);
    cin>>t;
    while(t--)
    {
        cin>>l>>r;
        cout<<dfs(2,1)<<endl;
    }
    return 0;
}

其实还有很大优化的余地，为什么呢？23456789这8个数字每种若干的组合等价于2357这四个数字，别的都可以由2357表示出来。如果组合数学好的话，恐怕是可以直接枚举2357然后计算出所有的可能的！不会算的话，利用这个性质以及多组数据的性质，可以把爆搜改成记忆化搜索， $dfs(l,r)$dfs(l,r)表示乘起来是 $[l,r]$[l,r]范围的数的个数。
用映射存了 $dfs(l,r)$dfs(l,r)，320ms，用map<pair<ll,ll>,ll>也可以。

#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define mod 1000000007 
#define cal(l,r) (l*(1LL<<40)+r)
 
ll t,l,r;
map<ll,ll> dp;

ll dfs(ll l,ll r)
{
    if(dp.count(cal(l,r)))return dp[cal(l,r)];
    if(l>r)return 0;
    if(l==1&&r==1)return dp[cal(l,r)]=1;
    ll ans=(l==1);
    for(int i=2;i<=9;i++)
    {
        int newl=ceil(1.0*l/i),newr=r/i;
        ans=(ans+dfs(newl,newr))%mod;
    }   
    return dp[cal(l,r)]=ans;
}
 
int main()
{
   // freopen("input.in","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>l>>r;
        if(l==1)l++;
        cout<<dfs(l,r)<<endl;
    }
    return 0;
}