为什么这位大佬只初始化一遍?
#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 //狂三我老婆,不服憋着
}
代码来源:第一篇题解