题解 P4127 【[AHOI2009]同类分布】

数据范围明示数位dp
先考虑将题目转化为求两次$1 - x$之间的符合条件的数的个数后相减
对于求一次的过程，我们先枚举数字之和$mod$，再直接进行dp即可
状态为$dp_{op,sum,st,limit}$，其中$op$表示当前位数，$sum$表示当前数位之和，$st$表示当前数对$mod$取模后的值，$limit$表示在之前是否取到最大值
时间复杂度$O(n^4*9^3)$，对于$n=18$可以在3s内通过
代码：

#include<iostream>
#include<cstring>
using namespace std;
long long dp[20][200][200][2];
int a[20],mod;
long long dfs(int k,int s,int st,bool limit){
	if(k<=0)return (st==0)&&(s==mod);
	if(dp[k][s][st][limit]!=-1)return dp[k][s][st][limit];
	int mx=(limit==1)?a[k]:9;
	long long ans=0;
	for(int i=0;i<=mx;i++){
		ans+=dfs(k-1,s+i,(st*10+i)%mod,(i==mx)&&limit);
	}
	return dp[k][s][st][limit]=ans;
}
long long solve(long long k){
	int cnt=0;
	while(k>0){
		a[++cnt]=k%10;
		k/=10;
	}
	long long ans=0;
	for(mod=1;mod<=cnt*9;mod++){
		memset(dp,-1,sizeof(dp));
		ans+=dfs(cnt,0,0,1);
	}
	return ans;
}
int main(){
	long long l,r;
	cin>>l>>r;
	cout<<solve(r)-solve(l-1);
	return 0;
}