题解 CF55D 【Beautiful numbers】

· · 题解

这题做了半天。美丽的数的定义是“可以被自己的所有非零数位整除的数”。做数位DP，想的就是每个状态需要什么参量来表示。注意到这个定义的限制并不在选取每个数位的时候，而是在整个数字选完之后才能做一个整体判断。

很自然地，首先想到需要知道我们已经在2, 3, \dots, 9中选了哪些数字，这可以用一个7位二进制数来表示。这个想法虽然正确，但在本题中时间效率不够。能够观察到，假如我们选了9而没有选3，这种情况在最后需要的判断，和既选了9也选了3是等价的。这不免让我们意识到，可以拿我们已选的所有数位在2, 3, 5, 7的最高次幂分别作为一个状态参量，它一共有4\times3\times2\times2=48种可能取值，比一个7位二进制数来得小很多。这样做其实是可以的，但写起来稍微麻烦一点。我们依然可以更进一步：能够被我们的所有数位整除，就等价于能够被我们的所有数位的最小公倍数整除。虽然这个最小公倍数最大能达到2520，但根据刚才的论述，它只有48个可能的取值，对应的是2520的所有因数，简单离散化即可。

我们需要判断的是整个数能否被所有数位的最小公倍数整除。最理想的做法是记录状态参量包括“每一步选完后的数前缀”模“我们所选的所有数位的最小公倍数”的值。但这是不可能的，因为在选取的每一步，我们无法预知后面的步骤会选择什么，也就无法预知这个最小公倍数是几。但所幸其实只要是这个最小公倍数的倍数作为模数，我们都可以用余数来判断原数对最小公倍数的整除性。因此最后我们选取的模数相等于是“所有最小公倍数的最小公倍数”，不难发现这个虚张声势的说法等价于2, 3, \dots, 9的最小公倍数2520。

理论上这道题就做完了。但是我又被卡时间了。这时候我意识到数位DP未必非要走套路：先求小于等于n的“满足条件的数”，再拿区间两个端点求出的值减一下——其实可以搜索的时候同时卡两个端点，然后一遍就搜完了。做法就是不仅记录“已选择的所有数中是否均和右端点对应数位相等”，也记录“已选择的所有数中是否均和左端点对应数位相等”，这两个状态分别影响每一步能选择的数的上界和下界。这么做的好处在于，由此搜索的复杂度就只和区间长度有关，和左右端点数的大小本身无关了。换言之，对于原先左右端点都很大、但区间长度未必大的数据，这样做显然能缩短运行时间；对于其他数据，也不会明显劣于之前的算法（未严格证明）。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=(int)from;i<=(int)to;++i)
#define For(i,to) for(register int i=0;i<(int)to;++i)
typedef long long ll;
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9' || c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}
const ll M = 2520;

ll l, r;
ll f[20][50][2521];
int fac[2521];
int dim_l[25]; int dim_l_size;
int dim_r[25]; int dim_r_size;

int gcd(int a, int b){ return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a / gcd(a, b) * b;}

ll dp(int x, int scm, int st, int opl, int opr) {
    if (x == -1) { return (st % scm) == 0; }
    ll &mem = f[x][fac[scm]][st];
    if (!opl && !opr && mem > -1) return mem;
    ll ret = 0;
    int maxx = opr ? dim_r[x] : 9;
    int minx = opl ? dim_l[x] : 0;
    rep(i, minx, maxx) {
        ret += dp(x - 1, (i == 0) ? scm : lcm(i, scm), ((st * 10 + i) % M), 
            (opl & (i == minx)), (opr & (i == maxx)));
    }
    if(!opl && !opr) mem = ret;
    return ret;
}

inline void cal_dim(ll n, int* dim, int &dim_size) {
    dim_size = 0;
    while(n) {
        dim[dim_size++] = n % 10; n /= 10;
    }
}

ll solve(ll l, ll r) {
    memset(dim_l, 0, sizeof(dim_l));
    memset(dim_r, 0, sizeof(dim_r));
    cal_dim(l, dim_l, dim_l_size);
    cal_dim(r, dim_r, dim_r_size);
    memset(f, -1, sizeof(f));
    return dp(dim_r_size-1, 1, 0, 1, 1);
}

int main() {
#ifdef D
    freopen("CF55D.in", "r", stdin);
    double TIMEA = clock();
#endif

    int cnt = 0;
    for(int i = 1; i <= M; ++i) {
        if (M % i == 0) fac[i] = ++cnt;
    }

    int T; T = read();
    while(T--) {
        l = read(); r = read();
        ll ans = solve(l, r);
        cout << ans << "\n";
    }

#ifdef D
    double TIMEB=clock();
    printf("\n# Time consumed: %.3fs.\n", (TIMEB-TIMEA)/1000);
#endif
    return 0;
}