P10959 月之谜 题解

· · 题解

Solution

数位 dp 板子。

设 dp_{i,j,k,p} 表示正在填从高到低的第 i 位，之前数位和为 j，固定模数为 p，模剩下的是 k。

那么枚举当前位要填的数字 k，继续往下递归求解就好了。边界情况为 i=0 时若 j=p 且 k=0 时为 1，否则为 0。

在最外面枚举每次固定的模数，就做完了。

Code

#include<stdio.h>
#include<string.h>
int dp[11][91][91][91];
int a[11],len;
int dfs(int dep,int sum,int num,int mod,bool lim){
    if(!dep)return sum==mod&&!num;
    if(!lim&&~dp[dep][sum][num][mod])return dp[dep][sum][num][mod];
    int res=0;
    const int up=lim?a[dep]:9;
    for(int i=0;i<=up;++i)
        if(sum+i<=mod)res+=dfs(dep-1,sum+i,((num<<3)+(num<<1)+i)%mod,mod,lim&(i==a[dep]));
    if(!lim)dp[dep][sum][num][mod]=res;
    return res;
}
inline int solve(int n){
    len=0;
    for(int i=n;i;i/=10)a[++len]=i%10;
    int res=0;
    for(int i=9*len;i;--i)
        res+=dfs(len,0,0,i,1);
    return res;
}
int l,r;
int main(){
    memset(dp,-1,sizeof(dp));
    while(~scanf("%d%d",&l,&r))
        printf("%d\n",solve(r)-solve(l-1));
    return 0;
}