#10166. 「一本通 5.3 练习 1」数字游戏

#10166. 「一本通 5.3 练习 1」数字游戏 - 题目 - LibreOJ (loj.ac)

数位DP模板

DP维度：pos，sum，lim，zero

sum表示当前所有枚举的数之和%MOD后的值，否则dp这维度是存不下滴

如果枚举完了 sum=0 并且 不是全是前导零 的情况，返回1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   //vector函数
#define popb pop_back  //vector函数
#define fi first
#define se second
const int N=200;
//const int M=;
//const int inf=0x3f3f3f3f;     //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int l,r,MOD,len,a[N],dp[N][N][2][2];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int dfs(int pos,int sum,bool lim,bool zero)
{
    if(pos==len+1)
    {
        if(!sum&&!zero) return 1;
        return 0;
    } 
    if(dp[pos][sum][lim][zero]!=-1) return dp[pos][sum][lim][zero];
    int res=0,num=lim?a[pos]:9;
    for(int i=0;i<=num;i++)
        res+=dfs(pos+1,(sum+i)%MOD,lim && i==num,zero && i==0 );
    dp[pos][sum][lim][zero]=res; 
    return res;
} 
int solve(int x)
{
    len=0;
    memset(dp,-1,sizeof(dp));
    for(;x;x/=10) a[++len]=x%10;
    reverse(a+1,a+len+1);
    return dfs(1,0,1,1);
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    while(scanf("%d%d%d",&l,&r,&MOD)!=EOF) printf("%d\n",solve(r)-solve(l-1));
    return 0;
}