洛谷 P4127 [AHOI2009] 同类分布

思路

这大概是第一次写数位dp，看了些博客才写的

因为每次的数位之和都不大一样，所以每次只需枚举mod，也就是各位数字之和，然后记忆花搜索，n代表位数，limit代表每一位是否有上限，num代表枚举到的数模mod的值，sum代表现在数的数字和，所以若位数达到，sum与枚举的mod一样，并且可以整除（num%mod == 0）那么返回1

若每次limit == 0，代表没有限制，则可以赋值dp值，若有的话则会有limit限制，以后调用会出错。

每次dfs枚举0~9，（若有limit则更新上限）

然后就可以递归（n+1， sum+i， 0/1（limit）， num*10+i % mod）了

每次ans += dfs(1, 0, 1, 0)

代码：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300100
#define ll long long
ll dp[20][250][250], n, a, b, len[300], cnt, ans1, ans2, mod;
ll dfs(ll no, ll sum, ll num, ll limit)
{
	if(no > cnt)
	{
		if(sum == mod && num == 0) return 1;
		return 0;
	}
	if(limit == 0 && dp[no][sum][num] != -1) return dp[no][sum][num];
	ll nolimit = 9, nosum = 0;
	if(limit == 1) nolimit = len[cnt-no+1];
	for(int i=0;i<=nolimit;i++)
	{
		if(limit == 1 && i == nolimit) nosum += dfs(no+1, sum+i, (num*10+i)%mod, 1);
		else
			nosum += dfs(no+1, sum+i, (num*10+i)%mod, 0);
	}
	if(limit == 0) dp[no][sum][num] = nosum;
	return nosum;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	ll x=a-1, y=b;
	while(x) len[++cnt] = x%10, x/=10;
	for(ll i=1;i<=9*cnt;i++)
	{
		mod = i;
		memset(dp, -1, sizeof(dp));
		ans2 += dfs(1, 0, 0, 1);
	}
	memset(len, 0, sizeof(len));
	cnt=0;
	while(y) len[++cnt] = y%10, y/=10;
	for(ll i=1;i<=9*cnt;i++)
	{
		mod = i;
		memset(dp, -1, sizeof(dp));
		ans1 += dfs(1, 0, 0, 1);//代码里第四位是limit 
	}
	printf("%lld\n",ans1-ans2);//注意是ansr - ans(l-1) 
	
	return 0;
}