Codeforces 55D Beautiful numbers

题目链接:https://codeforces.com/problemset/problem/55/D

题意:输出[L,R]中满足这个数对它自己每一位非零数字都整除的数的个数.

思路:刚开始想了枚举数的集合然后数位DP但是实在是太慢了...看了题解才知道我们已知1..9的最小公倍数是2520,那么我们假设要求数xy是等于0的,然后我们改写xx=x\bmod 2520+2520*k已知2520一定整除y所以问题就转化成x\bmod 2520是否整除它数位上的每一个非零的数字,定义dp[i][j][S][k]表示从高到低考虑前i个数位模2520j,已经出现的非零的数字集合为S,当前i是否等于n的情况为k的方案数然后DP,记忆化搜索去掉最后一维去搜索即可,注意到什么数都整除1所以只要考虑[2,9]即可.

#include <bits/stdc++.h>
#define MP make_pair
#define PB emplace_back
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int P=2520;
int T,status,i,digit[20];
ll l,r,ans,dp[20][256][2520];
ll dfs(int pos,int S,int num,bool jud){
    if (!pos){
        for (int i=0;i<8;++i)if(S&(1<<i)){
            if (num%(i+2)) return 0;
        }
        return 1;
    }
    if (!jud && ~dp[pos][S][num]) return dp[pos][S][num];
    int limit=jud?digit[pos]:9;
    ll ret=0;
    for (int i=0;i<=limit;++i){
        ret+=dfs(pos-1,i>1?S|(1<<(i-2)):S,(num*10+i)%P,jud && i==limit);
    }
    if (!jud) dp[pos][S][num]=ret;
    return ret;
}
ll cal(ll x){
    if (!x) return 1;
    int len=0;
    while (x){
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,0,0,1);
}
int main(){
    memset(dp,-1,sizeof(dp));
    for (read(T);T--;){
        read(l),read(r);
        printf("%lld\n",cal(r)-cal(l-1));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注