1799: [Ahoi2009]self 同类分布

Time Limit: 50 Sec Memory Limit: 64 MB
Submit: 2357 Solved: 1079
[Submit][Status][Discuss]

Description

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

Sample Input

10 19

Sample Output

HINT

【约束条件】1 ≤ a ≤ b ≤ 10^18

Source

Day1

[Submit][Status][Discuss]

qingdaobaibai的题解

因为考虑到直接dp不可行，我们先枚举数字之和，共有9*18种，f[i][j][k][2]表示长度为i数字之和为j，模当前枚举的数字之和为k的是否严格小于该数的种类数。

那么f[i][j][k]-->f[i+1][j+p][(k*10+p)%mod]大概就是这样

#include<bits/stdc++.h>

#define rg register

#define il inline

#define co const

template<class T>il T read(){

    rg T data=0,w=1;rg char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}

    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();

    return data*w;

}

template<class T>il T read(rg T&x) {return x=read<T>();}

typedef long long ll;

co int N=200,L=21;

ll f[L][N][N][2];

int n[L];

ll calc(ll x,int P){

	if(!x) return 0;

	memset(f,0,sizeof f);

	int t=0;

	while(x) n[++t]=x%10,x/=10;

	f[t+1][0][0][0]=1;

	for(int i=t+1;i>1;--i)

		for(int j=0;j<=P;++j)

			for(int k=0;k<P;++k)if(f[i][j][k][0]||f[i][j][k][1])

				for(int p=0;p<10;++p){

					int w=(10*k+p)%P;

					if(p<n[i-1]&&j+p<=P) f[i-1][j+p][w][1]+=f[i][j][k][0];

					else if(p==n[i-1]&&j+p<=P) f[i-1][j+p][w][0]+=f[i][j][k][0];

					if(f[i][j][k][1]&&j+p<=P) f[i-1][j+p][w][1]+=f[i][j][k][1];

				}

	return f[1][P][0][0]+f[1][P][0][1];

}

int main(){

	ll a=read<ll>(),b=read<ll>(),ans=0;

	for(int i=1;i<=9*18;++i) ans+=calc(b,i)-calc(a-1,i);

	printf("%lld\n",ans);

	return 0;

}