Luogu P4127 [AHOI2009]同类分布

数位DP
这题最妙的一点在于，由于我们无法存下原来的这个数，我们就考虑存取模之后的值，而这个模数就选择一个可能是最后的每一位数字的和的值。而这个总数只有\(9*18=162\)种，然后存下每一位的和以及从高位到低位的取模结果，数位DP即可。

#include <cstdio>
#include <cstring>
using namespace std;
#define R register
#define LL long long 

LL dp[20][200][200];
int st[20],len;

inline LL dfs(int now,int lead,int top,int sum,int yu,int Mod) {
	//printf("%d %d %d %d\n",now,sum,yu,Mod);//return 0;
	if(now==0) {
		if(sum==Mod&&yu==0) return 1;
		return 0;
	}
	
	if(!top&&!lead&&dp[now][sum][yu]!=-1) return dp[now][sum][yu];
	
	int up=top?st[now]:9;
	LL ans=0;
	//printf("%d\n",up);
	for(R int i=0;i<=up;i++)
		ans+=dfs(now-1,lead&&i==0,top&&i==up,sum+i,(yu*10+i)%Mod,Mod);
	//	printf("32");
	if(!top&&!lead) dp[now][sum][yu]=ans;
	return ans;
}

inline LL solve(LL x) {
	len=0;
	while(x)  { st[++len]=x%10; x/=10; }
	LL ans=0;
	for(R int sum=1;sum<=162;sum++) {
		memset(dp,-1,sizeof(dp));
		ans+=dfs(len,1,1,0,0,sum);
	}
	//dfs(2,1,1,0,0,0);1
	return ans;
}

int main() {
	LL a,b;
	scanf("%lld%lld",&a,&b);//printf("%d %d\n",a,b);
	printf("%lld\n",solve(b)-solve(a-1));
	return 0;
}

Luogu P4127 [AHOI2009]同类分布

原文：https://www.cnblogs.com/HN-wrp/p/12822026.html