2017-04-02

【bzoj1799】同类分布

数位dp重修系列第二题

AC通道

这道题方法很妙，get到了一些经验

我们发现数位之和在1~162的范围内，所以可以直接枚举数位和sum

然后用f[i][j][k]记录前i位的数位和为j，且当前数模sum等于k，那么判断合法的条件就是j==sum&&k==0

#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
int sum,num[20];
ll ans,f[20][170][170];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
ll dfs(int i,int j,int k,int flag){
	if(j>sum)  return 0;
	if(!i)  return (j==sum&&!k);
	if(!flag&&f[i][j][k]!=-1) return f[i][j][k];
	ll temp=0;
	for(int x=0;x<=(flag?num[i]:9);++x)
		temp+=dfs(i-1,j+x,(k*10+x)%sum,flag&&x==num[i]);
	if(!flag)  f[i][j][k]=temp;
	return temp;
}
ll cal(ll x){
	int tot=0;  memset(f,-1,sizeof(f));
	while(x) num[++tot]=x%10,x/=10;
	if(tot*9<sum)  return 0;
	return dfs(tot,0,0,1);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	ll l=read(),r=read();
	for(int i=1;i<=162;++i) sum=i,ans+=cal(r)-cal(l-1); 
	printf("%lld\n",ans);
	return 0;
}

本文标题:【bzoj1799】同类分布

文章作者:chty

发布时间:2017年04月02日 - 11时41分

最后更新:2018年03月02日 - 17时28分

许可协议:本文为博主原创，未经许可不得转载。