1. 首页
2. 数位DP
3. 本页

CodeForces 55D Beautiful numbers (数位DP)

居然可以这样处理orz~~~

下面为转载内容：

a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.
问一个区间内[l,r]有多少个Beautiful数字
范围9*10^18

数位统计问题，构造状态也挺难的，我想不出，我的思维局限在用递推去初始化状态，而这里的状态定义也比较难
跟pre的具体数字有关

问了NotOnlySuccess的，豁然开朗  Orz

一个数字要被它的所有非零位整除，即被他们的LCM整除，可以存已有数字的Mask，但更好的方法是存它们的LCM{digit[i]}
int MOD = LCM{1,2,9} = 5 * 7 * 8 * 9 = 2520
按照定义，数字x为Beautiful ：
x % LCM{digit[xi]} = 0
即 x % MOD % LCM{digit[xi]} = 0
所以可以只需存x % MOD，范围缩小了
而在逐位统计时，假设到了pre***（pre指前面的一段已知的数字，而*是任意变）
( preSum * 10^pos + next )  % MOD % LCM(preLcm , nextLcm)
=  ( preSum * 10 ^ pos % MOD + next % MOD ) % LCM(preLcm , nextLcm)
== 0
而next，nextLcm是变量，上面的比较式的意义就是
在已知pos , preSum , preLcm情况下有多少种(next,nextLcm)满足式子为0
而这个就是一个重复子问题所在的地方了，需要记录下来，用记忆化搜索
dfs(pos , preSum , preLcm , doing)
加一个标记为doing表示目前是在计算给定数字的上限，还是没有上限，即***类型的
这样就将初始化以及逐位统计写在一个dfs了，好神奇！！！

还有一点，10以内的数字情况为2^3 , 3^2 , 5 , 7
所以最小公倍数组合的情况只有4*3*2*2 = 48
可以存起来，我看NotOnlySuccess的写法是
for(int i = 1 ; i <= MOD ; i ++)
{
if(MOD % i == 0)
index[i] = num++;
}
很棒！！

所以复杂度大概为19*2520*48*10（状态数*决策数）

我觉得这题状态的设计不能跟具体数字分开，否则会很难设计吧
所以用记忆化搜索，存起来
用具体数字去计算，重复的子问题跟pre关系比较密切
有一个比较重要的切入点就是LCM，还有%MOD缩小范围，才能存储

还有优化到只需%252的，更快
不过我觉得%2520比较好理解

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int MOD = 2520;
const int MAXN = 320000+10;

LL dp[25][MOD][55];
int dig[25];
int tmp[MOD+10];

void init()
{
    int t=0;
    for(int i=1; i<=MOD; ++i)
    {
        if(MOD%i==0)
        {
            tmp[i]=t++;
        }
    }
}

LL gcd(LL a,LL b)
{
    return b == 0 ? a : gcd(b, a%b);
}

LL lcm(LL a,LL b)
{
    return a/gcd(a,b)*b;
}

LL dfs(int len,int sum,int prelcm,bool mxl)
{
    if(!len)
    {
        return (sum%prelcm)==0;
    }
    if(!mxl && dp[len][sum][tmp[prelcm]]!=-1)
    {
        return dp[len][sum][tmp[prelcm]];
    }
    LL res=0;
    int maxlen=mxl?dig[len]:9;
    for(int i=0; i<=maxlen; ++i)
    {
        int nowlcm=prelcm;
        int nowsum=(sum*10+i)%MOD;
        if(i)
        {
            nowlcm=lcm(prelcm,i);
        }
        res+=dfs(len-1,nowsum,nowlcm,mxl&& i==maxlen);
    }
    if(!mxl)
    {
        dp[len][sum][tmp[prelcm]]=res;
    }
    return res;
}


LL solve(LL x)
{
    memset(dig,0,sizeof(dig));
    int len=0;
    while(x)
    {
        dig[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,1,true);
}


int main()
{
    init();
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));//记忆化！清空一次就可以了
    while(t--)
    {
        LL l,r;
        cin>>l>>r;

        cout<<(solve(r)-solve(l-1))<<endl;
    }
    return 0;
}