15011418730 LV 7 @ 2025-8-24 22:14:53

自动搬运

来自洛谷，原作者为

	slgdsxw **

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

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

以下是正文

Update on 2020.5.31：极大简化了代码，跑的飞快

小蒟蒻的第一篇题解，望大家支持，如有排版格式问题还请见谅。

此题比较复杂，做的话需要先熟悉数位dp的基本套路，我们慢慢分析。

看到 “各位数字之积” 应该可以想到这是数位dp题，那么最朴素的想法就是 $f(i,j)$ 表示前 $i$ 位数各位数字之积为 $j$ 时的答案， $j$ 最大 $10^{18}$ ，无法通过。

考虑到 K 为 1-9 这些数字的乘积（我们先忽略0），K的质因子就只有 2,3,5,7 四个，因此我们可以用四个下标 a , b , c , d 来表示 $j$ ，即 $j=2^a * 3^b * 5^c * 7^d$ ,但是把四个参数都写到dp数组里的话状态数还是有点大，达到了 1e8 的级别。

为了减少复杂度我们先预处理出 $10^{18}$ 所有以内所有可能的 $j$ （ $j=2^a * 3^b * 5^c * 7^d$ ） ,它可以很暴力（~~反正数很少~~），如下：

	int lim2=59,lim3=37,lim5=25,lim7=21;
	ll fac2[60],fac3[60],fac5[60],fac7[60];
	fac2[0]=fac3[0]=fac5[0]=fac7[0]=1;
	fac[0]=1;
	for(int i=1;i<=lim2;i++)fac2[i]=fac2[i-1]*2;
	for(int i=1;i<=lim3;i++)fac3[i]=fac3[i-1]*3;
	for(int i=1;i<=lim5;i++)fac5[i]=fac5[i-1]*5;
	for(int i=1;i<=lim7;i++)fac7[i]=fac7[i-1]*7;
	for(int i=1;i<=18;i++)fac[i]=fac[i-1]*10;
	maxk=fac[18];
	for(int i=1;i<=18;i++)fac[i]%=mod;
	for(int i=0;i<=lim2;i++)
		for(int j=0;j<=lim3&&fac2[i]*fac3[j]<=maxk;j++)
			for(int k=0;k<=lim5&&fac2[i]*fac3[j]*fac5[k]<=maxk;k++)
				for(int l=0;l<=lim7&&fac2[i]*fac3[j]*fac5[k]*fac7[l]<=maxk;l++)
					num[++kcnt]=fac2[i]*fac3[j]*fac5[k]*fac7[l];
	sort(num+1,num+kcnt+1);

为了转移方便，某个 $j$ 与1-9中的某数运算的结果在数表num中的位置我们也需要知道，预处理出来， $p_{0-3}$ 对应着2,3,5,7。

	for(int i=1;i<=kcnt;i++)to[i][1]=i;
	for(int i=0;i<=3;i++)
		for(int j=1;j<=kcnt;j++)
			if(num[j]%p[i]==0)to[j][p[i]]=id(num[j]/p[i]);
	for(int i=4;i<=9;i++)
	{
		if(i==p[0]||i==p[1]||i==p[2]||i==p[3])continue;
		for(int j=1;j<=kcnt;j++)to[j][i]=getto(j,i);
	}

其中 $to(i,j)$ 表示数表中第 $i$ 个数除以 $j$ 的结果在数表中的位置（注意是除不是乘，原因下面讲）id函数使用的stl的二分查找，getto是质因数分解求to的过程，如 $to(i,4)=to(to(i,2),2)$ 。代码如下：

int id(ll x)
{
	return lower_bound(num+1,num+kcnt+1,x)-num;
}
int getto(int x,int k)
{
	for(int i=0;i<=3;i++)
		while(k%p[i]==0)
		{
			k/=p[i];
			x=to[x][p[i]];
		}
	return x;
}

然后我们的dp状态就可以设计为 $f(i,j)$ 表示前 $i$ 位当前乘积为 $j$ 的答案数，因为如果没有数的大小限制，且没有前导零的影响， $f(i,j)$ 的值就只与最终数位的乘积K有关系。我们把 $f(i,j)$ 的含义改一下，表示到了第 $i$ 位，还需要的数位乘积为 $j$ 的答案，那么 $f(i,j)$ 的值与K也没有了关系（把K当初始值来看）。我们求答案用到 $f$ 的时候已经有小于上界和无前导零的条件，这两维不用考虑。

我们再关注一下这个题要求什么：满足题意数的和。如果求个数的话就很简单了，和怎么求呢？我们还要加入一个数组g， $f,g$ 的最终含义： $f(i,j)$ 表示到了第 $i$ 位，还需要的数位乘积为 $j$ 时的方案数： $g(i,j)$ 表示到了第 $i$ 位，还需要的数位乘积为 $j$ 时可以填的数的和（中间两维我略了）。这个 $g$ 指的数是从第 $i$ 位开始计的，比如 $i=3$ ，后三位可以填123,213,321这三个数,，那么 $f$ 的值为3， $g$ 的值即为 $123+213+321$

$f(i,j),g(i,j)$ 如何转移呢？ $f$ 的值可以直接从下一位累加，假设第 $i$ 位我们填了a，后面还有3位， $g$ 计算的和即为形如aXXX这样的数的和，这个XXX每有一种方案, $g$ 就加上 $1000a$ 而后面这些可能的XXX的总和恰是下一位的 $g$ 要所表示的，XXX的方案数则由下一位的 $f$ 表示，那么这个预先dp就可以写出了（边界值按 $f,g$ 的定义很好考虑, $fac(i)$ 为 $10^i$ ：

void dp(int k,int rest)
{
	if(!k)
	{
		f[k][rest]=(rest==1);
		g[k][rest]=0;
		return;
	}
	if(f[k][rest]!=-1)return;
	ll rf=0,rg=0;
	int a1,a2;
	for(int i=9;i>=1;i--)
	{
		a1=k-1;
		a2=(i==0)?rest:to[rest][i];
		if(!a2)continue;
		dp(a1,a2);
		rf+=f[a1][a2];
		rg=(rg+i*f[a1][a2]*fac[k-1]+g[a1][a2])%mod;
	}
	f[k][rest]=rf%mod;
	g[k][rest]=rg;
	return;
}

剩余的数位乘积是减少的， $to$ 在这里就用上了（这就是为什么 $to$ 处理的是除）。

需要 $f,g$ 的值时调用这个dp：

if(f[k][rest]==-1)dp(k,rest);

那么对于输入的A,B,K，先转化成前缀相减：

cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;

在上界的限制下dfs每一位填什么，并传递当前前缀值，如果满足已经小于上界、没有前导零影响了，直接返回答案，计算方法与 $g$ 的推导类似，可以把当前的前缀值pre看做我们刚才讨论 $g$ 时的a。dfs代码如下：

ll dfs(int k,int low,int zero,int rest,ll pre)
{
	if(!rest)return 0;
	if(low&(!zero))
	{
		if(f[k][rest]==-1)dp(k,rest);
		return (pre*fac[k]%mod*f[k][rest]+g[k][rest])%mod;
	}
	if(!k)return pre*(rest==1);
	ll res=0;
	for(int i=low?9:a[k];i>=(!zero);i--)
		res+=dfs(k-1,low|(i<a[k]),zero&(i==0),(i==0)?rest:to[rest][i],(pre*10+i)%mod);
	return res;
}

这个题做完了？似乎我们还忽略了零。。。

如果 $K=0$ ,问题可以看做求在A到B中所有至少有一位为零的数的和，（~~和上面那些比这还不简单~~）与 $f,g$ 的定义类似， $f0(i,j,k,l)$ 表示到了第 $i$ 位是（1）否（0）小于上界值，是（1）否（0）有前导零，前面已经有 $l$ 个零时的填的方案数， $g0$ 表示填的数的和，注意前导零。

void dp0(int k,int low,int zero,int cnt0)
{
	if(!k)
	{
		f0[k][low][zero][cnt0]=(cnt0>0);
		g0[k][low][zero][cnt0]=0;
		return;
	}
	if(f0[k][low][zero][cnt0]!=-1)return;
	ll rf=0,rg=0;
	int b1,b2,b3,b4;
	for(int i=low?9:a[k];i>=0;i--)
	{
		b1=k-1;
		b2=low|(i<a[k]);
		b3=zero&(i==0);
		b4=cnt0+((!zero)&(i==0));
		dp0(b1,b2,b3,b4);
		rf=(rf+f0[b1][b2][b3][b4])%mod;
		rg=(rg+i*f0[b1][b2][b3][b4]*fac[k-1]%mod+g0[b1][b2][b3][b4])%mod;
	}
	f0[k][low][zero][cnt0]=rf;
	g0[k][low][zero][cnt0]=rg;
	return;
}

还有一些细节如判断K是否可以被2,3,5,7质因数分解等不一一赘述了，看完整代码吧，少用些取模运算速度提升很大。

感觉自己写的复杂度很高，常数很大，有可优化之处还望各位dalao赐教qwq。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#define ll long long
using namespace std;
const int mod=20120427;
int kcnt;
int to[70000][10],a[20],p[4]={2,3,5,7};
ll l,r,K,maxk;
ll fac[20],num[70000],f[20][70000],g[20][70000];
ll f0[20][2][2][20],g0[20][2][2][20];
int id(ll x)
{
	return lower_bound(num+1,num+kcnt+1,x)-num;
}
int getto(int x,int k)
{
	for(int i=0;i<=3;i++)
		while(k%p[i]==0)
		{
			k/=p[i];
			x=to[x][p[i]];
		}
	return x;
}
void dp(int k,int rest)
{
	if(!k)
	{
		f[k][rest]=(rest==1);
		g[k][rest]=0;
		return;
	}
	if(f[k][rest]!=-1)return;
	ll rf=0,rg=0;
	int a1,a2;
	for(int i=9;i>=1;i--)
	{
		a1=k-1;
		a2=(i==0)?rest:to[rest][i];
		if(!a2)continue;
		dp(a1,a2);
		rf+=f[a1][a2];
		rg=(rg+i*f[a1][a2]*fac[k-1]+g[a1][a2])%mod;
	}
	f[k][rest]=rf%mod;
	g[k][rest]=rg;
	return;
}
void init()
{ 
	int lim2=59,lim3=37,lim5=25,lim7=21;
	ll fac2[60],fac3[60],fac5[60],fac7[60];
	fac2[0]=fac3[0]=fac5[0]=fac7[0]=1;
	fac[0]=1;
	for(int i=1;i<=lim2;i++)fac2[i]=fac2[i-1]*2;
	for(int i=1;i<=lim3;i++)fac3[i]=fac3[i-1]*3;
	for(int i=1;i<=lim5;i++)fac5[i]=fac5[i-1]*5;
	for(int i=1;i<=lim7;i++)fac7[i]=fac7[i-1]*7;
	for(int i=1;i<=18;i++)fac[i]=fac[i-1]*10;
	maxk=fac[18];
	for(int i=1;i<=18;i++)fac[i]%=mod;
	for(int i=0;i<=lim2;i++)
		for(int j=0;j<=lim3&&fac2[i]*fac3[j]<=maxk;j++)
			for(int k=0;k<=lim5&&fac2[i]*fac3[j]*fac5[k]<=maxk;k++)
				for(int l=0;l<=lim7&&fac2[i]*fac3[j]*fac5[k]*fac7[l]<=maxk;l++)
					num[++kcnt]=fac2[i]*fac3[j]*fac5[k]*fac7[l];
	//cout<<kcnt<<endl;
	sort(num+1,num+kcnt+1);
	for(int i=1;i<=kcnt;i++)to[i][1]=i;
	for(int i=0;i<=3;i++)
		for(int j=1;j<=kcnt;j++)
			if(num[j]%p[i]==0)to[j][p[i]]=id(num[j]/p[i]);
	for(int i=4;i<=9;i++)
	{
		if(i==p[0]||i==p[1]||i==p[2]||i==p[3])continue;
		for(int j=1;j<=kcnt;j++)to[j][i]=getto(j,i);
	}
	memset(f,-1,sizeof(f));
	return;
}
ll check(ll x)
{
	for(int i=0;i<=3;i++)
		while(x%p[i]==0)x/=p[i];
	return x;
}
ll dfs(int k,int low,int zero,int rest,ll pre)
{
	if(!rest)return 0;
	if(low&(!zero))
	{
		if(f[k][rest]==-1)dp(k,rest);
		return (pre*fac[k]%mod*f[k][rest]+g[k][rest])%mod;
	}
	if(!k)return pre*(rest==1);
	ll res=0;
	for(int i=low?9:a[k];i>=(!zero);i--)
		res+=dfs(k-1,low|(i<a[k]),zero&(i==0),(i==0)?rest:to[rest][i],(pre*10+i)%mod);
	return res;
}
void dp0(int k,int low,int zero,int cnt0)
{
	if(!k)
	{
		f0[k][low][zero][cnt0]=(cnt0>0);
		g0[k][low][zero][cnt0]=0;
		return;
	}
	if(f0[k][low][zero][cnt0]!=-1)return;
	ll rf=0,rg=0;
	int b1,b2,b3,b4;
	for(int i=low?9:a[k];i>=0;i--)
	{
		b1=k-1;
		b2=low|(i<a[k]);
		b3=zero&(i==0);
		b4=cnt0+((!zero)&(i==0));
		dp0(b1,b2,b3,b4);
		rf=(rf+f0[b1][b2][b3][b4])%mod;
		rg=(rg+i*f0[b1][b2][b3][b4]*fac[k-1]+g0[b1][b2][b3][b4])%mod;
	}
	f0[k][low][zero][cnt0]=rf;
	g0[k][low][zero][cnt0]=rg;
	return;
}
ll solve(ll x)
{
	int len=0;
	while(x)
	{
		a[++len]=x%10;
		x/=10;
	}
	return dfs(len,0,1,id(K),0);
}
ll solve0(ll x)
{
	int len=0;
	while(x)
	{
		a[++len]=x%10;
		x/=10;
	}
	memset(f0,-1,sizeof(f0));
	dp0(len,0,1,0);
	return g0[len][0][1][0];
}
int main()
{
	int T;
	init();
	cin>>T;
	while(T--)
	{
		cin>>l>>r>>K;
		if(!K)
		{
			cout<<((solve0(r)-solve0(l-1))%mod+mod)%mod<<endl;
			continue;
		}
		ll x=check(K);
		if(x!=1)
		{
			cout<<0<<endl;
			continue;
		}
		cout<<((solve(r)-solve(l-1))%mod+mod)%mod<<endl;
	}
	return 0;
}

ID

4848

时间

1000ms

内存

125MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

[SCOI2012] Blinker 的仰慕者

信息

1 条题解

自动搬运

以下是正文

[SCOI2012] Blinker 的仰慕者

信息

还没有账户？

登录