BZOJ1799 self 同类分布 数位dp

时间：2022-06-15 05:06:45

BZOJ1799self 同类分布

去博客园看该题解

题意

　　给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。
　　【约束条件】1 ≤ a ≤ b ≤ 10^18

题解

1.所有的位数之和<9*18=162
2.所以，dp[i][j][k][m]表示有i位（允许有前导0），数位和为k，模数为m，前i位与模数的模为j的符合条件的数的个数。这样要炸空间，怎么办！！其实这个dp的最后一维可以省去，因为对于不同的m值，dp互不相干。这样还是要超时的，有5亿多。于是就要卡常数，具体见代码里面的枚举的上下界。

代码

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long LL;

LL L,R;

LL dp[][][];

int a[],mod;

LL dfs(int d,int ds,int c,bool full){

    if (d==)

        return (ds==&&c==)?:;

    if (!full&&dp[d][ds][c]!=-)

        return dp[d][ds][c];

    LL ans=;

    int tp=min(ds,full?a[d]:);

    for (int i=max(,ds-*(d-));i<=tp;i++)

        ans+=dfs(d-,ds-i,(c*+i)%mod,full&&i==tp);

    if (!full)

        return dp[d][ds][c]=ans;

    return ans;

}

LL solve(LL n){

    if (n==)

        return ;

    int d=;

    while (n>)

        a[++d]=n%,n/=;

    LL ans=;

    for (int i=;i<=d*;i++){

        memset(dp,-,sizeof dp);

        mod=i;

        ans+=dfs(d,i,,);

    }

    return ans;

}

int main(){

    freopen("self.in","r",stdin);

    freopen("self.out","w",stdout);

    scanf("%lld%lld",&L,&R);

    printf("%lld",solve(R)-solve(L-));

    fclose(stdin);fclose(stdout);

    return ;

}

相关文章