bzoj 1799 同类分布

Written with StackEdit.

Description

给出(a,b)，求出([a,b])中各位数字之和能整除原数的数的个数。

Input

一行两个正整数,(a,b).

Output

([a,b])中各位数字之和能整除原数的数的个数.

Sample Input

10 19

Sample Output

3

HINT

(1 ≤ a ≤ b ≤ 10^{18}).

Solution

• 显然是一道数位(dp).
• 但这道题需要注意,计算前需要先确定模数,即数位总和,否则算出来的(f)值是在不同模数下的(f),无法转移.
• 注意到数位和最大为(9*18=162),所以从(1)到(162)依次枚举数位和,进行数位(dp)即可.只需注意最后的时候验证数位和是否为枚举的数位和即可.

#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline LoveLive read()
{
	LoveLive out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXSUM=162;
int n;
int t[20];
void split(LoveLive x)
{
	n=0;
	while(x)
		{
			t[++n]=x%10;
			x/=10;
		}
}
LoveLive f[20][200][200];
LoveLive dfs(int dep,int r,int sum,int mod,int limit)
{	
	if(dep==0)
		{
			if(r==0 && sum==mod)
				return 1;
			else
				return 0;
		}
	if(sum>mod)//可行性剪枝,其实还有其他剪枝,太懒没有打
		return 0;
	if(!limit && f[dep][r][sum]!=-1)
		return f[dep][r][sum];
	LoveLive res=0;
	int mx=limit?t[dep]:9;
	for(int i=0;i<=mx;++i)
		res+=dfs(dep-1,(10*r+i)%mod,sum+i,mod,limit && i==mx);
	if(!limit)
		f[dep][r][sum]=res;
	return res; 
}
LoveLive solve(LoveLive x)
{
	LoveLive res=0;
	split(x);
	for(int mod=1;mod<=MAXSUM;++mod)
		{
			memset(f,-1,sizeof f);
			res+=dfs(n,0,0,mod,1);
		}
	return res;
}
int main()
{
	LoveLive ans=0;
	LoveLive L=read(),R=read();
	ans+=solve(R);
	ans-=solve(L-1);
	printf("%lld
",ans);
	return 0;
}