关于这道题的初始化
查看原帖
关于这道题的初始化
308384
Morpheuse楼主2021/11/16 21:40

为什么这位大佬只初始化一遍?

#define Tokisaki return  //狂三我老婆!!!
#define Kurumi 0;      //狂三赛高!!!
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

#define rint register int   //加速用的,直接用int也可以
typedef long long ll;

using namespace std;

const int MOD=2520;
int t,book[MOD+1];
vector <int> shu;
ll l,r,dp[25][MOD+1][50];   //特别注意:DP数组一定要开long long类型,不然会炸

inline int gcd (int x,int y) //gcd函数,虽然STL里面自带(为__gcd),但还是自己手写了一个
{
	if(x>y) swap(x,y);
	if(y%x==0) return x;
	return gcd(x,y%x);
}

inline int _lcm (int x,int y)  //lcm函数,求最小公约数
{
	return x*y/gcd(x,y);
}

inline void init()         //初始化用的函数
{
	memset(dp,-1,sizeof(dp));  //将DP数组初始化
	rint num=0;
	for(rint i=1;i<=MOD;i++)   //离散化,将2520的因数们从1开始标记
	{
		if(MOD%i==0)
		{
			num++;
			book[i]=num;
		}
	}
}

ll dfs(int pos,int he,int lcm,int sp)  //数位DP主要内容
//pos:当前处理到第几位;     
//he:pos位之前的数%2520;
//lcm:pos位之前的数的每一位数的最小公倍数;
//sp:特判当前是否为范围内的最大值
{
	if(pos==-1) return he%lcm==0;    //如果处理完了最后一位,数如果满足条件,返回1,否则返回0
	if(sp==0&&dp[pos][he][book[lcm]]!=-1) return dp[pos][he][book[lcm]];      //如果不是最大值的情况,并且当前情况以处理过,直接返回值
	ll ans=0;
	int MAX=sp==1?shu[pos]:9;  //如果前几位是最大值情况,那么当前位最大值为这一位的数,否则为9
	for(rint i=0;i<=MAX;i++)  //从0枚举
	{
		int next_he=(he*10+i)%MOD;  //计算包含当前位时数的值
		int next_lcm=lcm;  
		if(i)
		{
			next_lcm=_lcm(next_lcm,i);//计算包含当前位时所有位上的数的最小公倍数(当前位所选数不为0,如果为零就是原数)
		}
		ans+=dfs(pos-1,next_he,next_lcm,sp&&i==MAX); //向下搜索,如果前几位是最大值情况,并且当前位为最大值时,sp=1
	}
	if(sp==0)   //如果不是最大值情况,记录运算结果
	{
		dp[pos][he][book[lcm]]=ans;
	}
	return ans;
}

inline ll work (ll num)   //处理数据加求值函数
{
	
	shu.clear();     //一定要记得清空
	while(num)       //将数值按为存入
	{
		shu.push_back(num%10);
		num/=10;
	}
	return dfs(shu.size()-1,0,1,1); //从最高位开始搜索
}

int main ()
{
	init();  //初始化
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>l>>r;
		cout<<work(r)-work(l-1)<<endl;
	}
	Tokisaki Kurumi   //狂三我老婆,不服憋着
}

代码来源:第一篇题解

2021/11/16 21:40
加载中...