自动搬运

查看原文

来自洛谷，原作者为

	Super_Cube AFO || 2020.09.20~2024.11.30 || 最后上线于 2024.12.31

搬运于2025-08-24 23:02:56，当前版本为作者最后更新于2024-10-06 22:15:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}