同类分布（数位DP入门）
题目描述
给出两个数a,b，求出[a,b]中各位数字之和能整除原数的数的个数。
输入格式
一行，两个整数a和b
输出格式
一个整数，表示答案
输入输出样例
输入
10 19
输出 #1复制
3
说明/提示
对于所有的数据，1 ≤ a ≤ b ≤ 10^18
解释
主函数
sss(n)-sss(m-1) 为了方便计算
SSS（）
对主函数传过来的值进行处理 然后进行 dfs
可以发现各位数之和最大只能是 9 * 18 = 162
我们可以枚举这个和 sum
然后去统计可以被 sum 整除，且数位和是 sum 的数。
我们把状态定义为 f[poo][tot][mod]
表示当前枚举到第 poo 位，目前这个数的数位和是 tot，对sum 取模是 mod.
如果满足：tot = sum 且 mod = 0，则要统计进答案。
我们可以枚举这个和 sum
然后去统计可以被 sum 整除，且数位和是 sum 的数。
我们把状态定义为 f[poo][tot][mod]
表示当前枚举到第 poo 位，目前这个数的数位和是 tot，对sum 取模是 mod.
如果满足：tot = sum 且 mod = 0，则要统计进答案。
dfs
1. poo 记录现在填到了多少位（递减）
2. tot 记录每位相加 % sum 的值
3. mod 记录现在这个数 % sum 的值
4. ed 记录现在填的数前面是否全部达到最大值
5. f[][][] 其实就是一个记忆化
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll m,n;
short a[100];
long long len;
long long sum;
long long f[20][400][400];
long long dfs(long long poo,long long tot,long long mod,long long ed)
{
if(tot>sum)
return 0;
if(!poo)
return mod==0&&tot==sum;
if(f[poo][tot][mod]!=-1&&!ed)
return f[poo][tot][mod];
long long g= ed?a[poo]:9;
long long ans=0;
for(long long i=0;i<=g;i++)
{
ans+=dfs(poo-1,tot+i,(mod*10+i)%sum,ed&&i==g);
}
if(!ed)
f[poo][tot][mod]=ans;//
return ans;
}
long long sss(long long p)
{
len=0;
while(p)
{
a[++len]=p%10;
p/=10;
}
long long ans=0;
for(long long i=1;i<=9*len;i++)
{
memset(f,-1,sizeof(f));
sum=i;
ans+=dfs(len,0,0,1);
}
return ans;
}
int main()
{
cin>>m>>n;
cout<<sss(n)-sss(m-1)<<endl;
return 0;
} 
投递去哪儿旅行等公司6个岗位
