ACWING 月之数/洛谷 同类分布

思路

通常而言数位DP都可以用记搜做,此题我们也考虑记搜

首先求出数字的和,去判断各位数字之和能否整除他的想法是错误的,因为每个数字都要判断一次,记搜变成暴搜。

转换思路,能够整除就是模数为0,所以可以考虑把每步的模数给算出来,算到最后一位判断模数是否为0即可

但是我们不知道各位数字之和是多少呀?没关系,不知道的枚举就好了。各位数字之和很小,可以直接暴力枚举,搜到最后一位时判断和是否为枚举的值。


C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=(a);i<=(b);++(i))
#define com(i,a,b) for(int i=(a);i>=(b);--(i))
#define mem(a,b) memset((a),(b),sizeof(a))
#define inf 0x3f3f3f3f
#define fin freopen("input.txt","r",stdin)
#define fout freopen("output.txt","w",stdout)
typedef long long ll;
const int maxn=100010;
int num[20],n,p;
ll f[20][200][200],_pow[20];

ll dfs(int len,int sum,bool limit,int mod){
    if(!len){
        if(sum==p&&!mod) return 1;
        return 0;
    }
    if(!limit&&f[len][sum][mod]!=-1) return f[len][sum][mod];
    int up=limit?num[len]:9;
    ll ret=0;
    go(i,0,up){
        ret+=dfs(len-1,sum+i,limit&&i==num[len],(mod*10+i)%p);
    }
    return f[len][sum][mod]=ret;
}

ll solve(ll val){
    n=0;
    while(val){
        num[++n]=val%10;
        val/=10;
    }
    ll ans=0;
    for(p=1;p<=200;p++)
    mem(f,-1),ans+=dfs(n,0,1,0);
    return ans;
}

signed main(){ 
    //fin;
    ll a,b;
    scanf("%lld%lld",&a,&b);
    printf("%lld",solve(b)-solve(a-1));
    return 0;
}

ACWING 月之数/洛谷 同类分布

上一篇:win10系统详细安装教程一


下一篇:Windows Server 2008 R2