Nowcoder 模拟赛 G1T2

2018-09-09 18:57:29


题意:定义 $f(x)$ 为 $x$ 各个数位的乘积,对于区间 $[l,r]$ ,求有多少个数满足 $L<=f(x)<=R$


数据范围是10^18,所以显然是一个数位dp的题目

这是第二次写数位dp

上一次用循环写的肥肠丑,这道题改用记忆化搜索

和一般的数位dp题目类似,用前缀和的思想

求出 $[0,r]$ 中满足条件的数和 $[0,l-1]$ 中满足条件的数,相减即可

求解时,dfs有四个参数

$pos$ 表示枚举到这个数的第几位

$sum$ 表示当前所有数位的乘积

$odk$ 表示这一位是否有大小限制(要控制在 $[l,r]$ 范围内)

$flag$ 表示这一位是否是前导零

用 $map$ 记录答案,枚举状态记忆化搜索即可

注意特判一下 $l=r=L=R=0$ 的情况,此时的答案需要 $+1$

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
ll l,r,L,R,ans,num,a[20];
map<ll,ll>mp[20];
inline void div(ll x){num=0; while (x) a[++num]=x%10,x/=10;}
ll dfs(ll pos,ll sum,bool odk,bool flag)
{
    if (!pos)
    {
        if (sum>=L&&sum<=R) return 1;
        return 0;
    }
    if (!odk&&flag&&mp[pos].count(sum)) return mp[pos][sum];
    ll now=odk?a[pos]:9,ans=0;
    if (flag)
    {
        for (int i=0;i<=now;i++)
          ans+=dfs(pos-1,sum*i,odk&&i==now,1);
    }
    else
    {
        ans+=dfs(pos-1,1,odk&&!now,0);
        for (int i=1;i<=now;i++)
          ans+=dfs(pos-1,sum*i,odk&&i==now,1);
    }
    if (!odk&&flag) mp[pos][sum]=ans;
    return ans;
}
int main()
{
    scanf("%lld%lld%lld%lld",&l,&r,&L,&R);
    if (l)
    {
        memset(a,0,sizeof(a)); div(l-1);
        for (int i=0;i<=18;i++) mp[i].clear();
        ans-=dfs(num,1,1,0);
    }
    if (r)
    {
        memset(a,0,sizeof(a)); div(r);
        for (int i=0;i<=18;i++) mp[i].clear();
        ans+=dfs(num,1,1,0);
    }
    printf("%lld\n",ans+((!L)&&(!l)));
    return 0;
}