Nowcoder 模拟赛 G1T2
Captain_Paul
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;
}
```