2017-04-02

【CF#55D】beautiful numbers

数位dp重修系列第一题

AC传送门

题目翻译

定义一个数是美丽的，当且仅当它能整除自身的每个非零数位。

例如 $250$ 是美丽的，$2333$ 就是不美丽的。

询问 $[L,R]$ 中有多少个数是美丽的。

$1≤L≤R≤9 \times 10^{18}$ 　

题解

考虑到 $1~9$ 的$LCM$只是$2520$，所以一个数的所有非零数位的$LCM$一定是$2520$的因数。

我们设当前状态为$f[i][j][k]$。

表示当前转移到了第$i$位，当前所有非零数位的$LCM$为$j$，当前这个数$%2520 = k$。

枚举当前位$x$。

那些状态可以转移到当前状态呢？

f[i-1][LCM(j,x)][(k*10+x)%2520]

因为$2520$的因数只有$48$个，所以把$lcm$这维优化成$48$这样空间就够了。

小结

数位dp代码的三种实现方式

１、预处理

预处理出所有的状态，然后枚举数位进行转移，转移时判断限制条件

优点：对于多组询问特别好用

缺点：对于有些题目可能很麻烦，甚至不能预处理

2、迭代

对于每次询问单独dp，记录限制条件

优点：代码好写（不用于处理，直接写一个dp就成）

缺点：多组询问没法处理

3、记忆化搜索

对于每一次询问DFS，如果这一位没有受到任何限制就记忆化

优点：代码更好写，且对于多组询问相对友好

缺点：如果位数特别大（什么1e5,1e6之类的），则效果可能不太好

所以以后做数位dp题目时，我首选第三种

比如说这道题：

#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
int cnt,num[25],p[55],id[2550],lcm[55][55];
ll f[25][55][2550];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll Lcm(ll a,ll b){return a*b/gcd(a,b);}
void pre(){
	for(int i=1;i<=2520;++i)if(!(2520%i))p[++cnt]=i; p[0]=1;
	for(int i=1;i<=cnt;++i)id[p[i]]=i;
	for(int i=0;i<=cnt;++i)for(int j=0;j<=cnt;++j)lcm[i][j]=id[Lcm(p[i],p[j])];
}
ll dfs(int i,int j,int k,bool flag){
	if(!i) return (k%p[j]==0);
	if(f[i][j][k]!=-1&&!flag)  return f[i][j][k];
	ll temp=0;
	for(int x=0;x<=(flag?num[i]:9);++x)
		temp+=dfs(i-1,lcm[j][x],(k*10+x)%2520,flag&&x==num[i]);
	if(!flag)  f[i][j][k]=temp;
	return temp;
}
ll get(ll x){
	int tot=0; memset(f,-1,sizeof(f));
	while(x) num[++tot]=x%10,x/=10;
	return dfs(tot,1,0,1);
}
void solve(){
	ll l=read(),r=read();
	printf("%I64d\n",get(r)-get(l-1));
}
int main(){
	//freopen(FILE".in","r",stdin);
	//freopen(FILE".out","w",stdout);
	pre();for(int T=read();T;--T) solve();
	return 0;
}

本文标题:【CF#55D】beautiful numbers

文章作者:chty

发布时间:2017年04月02日 - 10时48分

最后更新:2018年03月02日 - 17时43分

许可协议:本文为博主原创，未经许可不得转载。