自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:20:10，当前版本为作者最后更新于2020-04-12 15:59:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

首先题目中的$[A,B]$让我们可以直接联想到用数位dp做，可以设$dp_{i,j,k}$表示位数为$i$，在模$X$的意义下余数为$X-j$，是否含前导零用$k$表示的方案数，那么有转移方程（需要保证转移合法）：

初始状态：

但是貌似数据范围中$X\le10^{11}$不可做？如果$X\le 10^{5}$可以直接用数位dp，当$X> 10^{5}$时，$A/X\le 10^6,B/X\le 10^6$，可以直接枚举所有$X$的倍数，判断是否满足每一位都满足要求，如果满足答案直接累加就可以了。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
template<typename T>void read(T &x){
	x=0;int f(1);char c(getchar());
	for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
	for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c-'0');
	x*=f;
}
template<typename T>void write(T x){
	if(x<0)putchar('-'),x=-x;
	if(x/10)write(x/10),x%=10;
	putchar(x+'0');
}
const int maxn=15,maxx=100005;
int tmp[maxn],vis[10];
long long dp[maxn][maxx][2],X;
long long dfs(int pos,int le,int _0,int up){
	if(pos==-1)return _0==0&&le==0;
	if(!up&&(~dp[pos][le][_0]))
		return dp[pos][le][_0];
	long long ans=0;
	int mx=up?tmp[pos]:9;
	for(int i=1;i<=mx;++i){
		if(vis[i])
			ans+=dfs(pos-1,(le*10+i)%X,_0&&i==0,up&&i==tmp[pos]);
	}
	if(_0)ans+=dfs(pos-1,0,1,up&&tmp[pos]==0);
	else if(vis[0])ans+=dfs(pos-1,le*10%X,false,up&&tmp[pos]==0);
	if(!up)dp[pos][le][_0]=ans;
	return ans;
}
long long solve(long long test){
	int cnt=0;
	while(test){
		tmp[cnt++]=test%10;test/=10;
	}
	return dfs(cnt-1,0,1,1);
}
int judge(long long test){
	while(test){
		if(!vis[test%10])return false;
		test/=10;
	}
	return true;
}
int main(){
	long long A,B;
	read(X),read(A),read(B);
	char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())vis[c-'0']=true;
	if(X<=maxx){
		memset(dp,-1,sizeof dp);
		write(solve(B)-solve(A-1));
		putchar('\n');
	}
	else{
		int l=(int)((A-1)/X+1),r=(int)(B/X),ans=0;
		for(int x=l;x<=r;++x)
			if(judge(1ll*X*x))++ans;
		write(ans),putchar('\n');
	}
	return 0;
}

另：这可能并不是最优的写法，但是可以过这道题，欢迎大家想出更好的方法。

$\color{white}\text{看在我是第二个过这题的人份上，求过审qwq}$