P5842 Blinker的仰慕者
题面
思路
要每一位乘积为 ，很明显是一道数位 DP 题，首先这个数被质因数分解后一定只能有 这四个质因子，假如有其它质因子那么直接返回零，这个时候不存在答案。
所以我们就可以预处理一下所有的这种符合条件的数。
利用前缀和的思想，要求 之间的所有符合条件的数，其实就是求 的满足条件的数减去 的满足条件的数。
首先我们假设 不等于 ，那么符合条件的数除了前导零是不允许存在零的。
所以我们不如反着考虑，让这个满足条件的数不断除以 最后变成 。
所以定义 代表填到了第 位，还需要的乘积为 的方案数，相应地， 代表此时填的数之和。
从高到低枚举填的数，对于每次填的数，都对它进行一次 DP，相当于从高向低每一位填一个合法的数，然后对于当前已经填的数从低向高地处理它后面所有可能产生地答案的贡献，然后累加答案，这里的状态需要记录当前填到的位数，填的这些位置是小于还是等于上界，是否存在前导零，剩下还需要再乘多少，当前的前缀值。
当前这位如果要填零那么一定是前导零（我们的假设保证了数中不存在0），所以填零后剩下要乘的积不变，否则便除去当前的数，如果无法整除，那就直接返回对答案的贡献为零，而一个合法的数整除 我们可以预处理，详情见注释。
如果递归到了第零位，那么说明这个数已经填完了，就可以返回当前已经填完的数的编号。
再来考虑 的情况，这时候就是求所有存在一个非前导零的方案的总和，这个可以通过类似的 DP 解决，详情见注释。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=66666;
const int a=60,b=36,c=25,d=21;
const ll mod=20120427;
int f[19][N],g[19][N];//填到了第i位，还需要乘积为j的：方案数，可以填的数之和
ll f0[19][2][2][19],g0[19][2][2][19];//填到了第i位，是否小于上界，是否有前导零，前面已经有几个零：方案数，填的数之和
ll num[N];
ll n,l,r,k,cnt;
ll power_3[b+1],power_5[c+1],power_7[d+1],power_10[19];
int location[N][10],number[20];;//location[i][j]代表下标为i的数除以j得到的数的下标
inline ll read()
{
ll x=0,y=1;
char c=getchar();
while(c>'9'||c<'0')
{
if(c=='-') y=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*y;
}
bool check(ll x)
{
while(x%2==0) x>>=1;
while(x%3==0) x/=3;
while(x%5==0) x/=5;
while(x%7==0) x/=7;
if(x==1) return true;
return false;
}
void init()
{
power_3[0]=power_5[0]=power_7[0]=power_10[0]=1;
for(int i=1;i<=b;i++) power_3[i]=(power_3[i-1]<<1)+power_3[i-1];//位运算优化
for(int i=1;i<=c;i++) power_5[i]=(power_5[i-1]<<2)+power_5[i-1];
for(int i=1;i<=d;i++) power_7[i]=(power_7[i-1]<<3)-power_7[i-1];
for(int i=1;i<=18;i++) power_10[i]=power_10[i-1]*10;
ll maximum=power_10[18];
for(int i=1;i<=18;i++) power_10[i]%=mod;
for(int i=0;i<=a;i++)
for(int j=0;j<=b&&(power_3[j]<<i)<=maximum;j++)
for(int o=0;o<=c&&(power_3[j]*power_5[o]<<i)<=maximum;o++)
for(int p=0;p<=d&&(power_3[j]*power_5[o]*power_7[p]<<i)<=maximum;p++)
num[++cnt]=power_3[j]*power_5[o]*power_7[p]<<i;
sort(num+1,num+cnt+1);
for(int i=1;i<=cnt;i++)
{
location[i][1]=i;//除以1还是本身
if(num[i]%2==0) location[i][2]=(int)(lower_bound(num+1,num+1+cnt,num[i]/2)-num);
if(num[i]%3==0) location[i][3]=(int)(lower_bound(num+1,num+1+cnt,num[i]/3)-num);
if(num[i]%5==0) location[i][5]=(int)(lower_bound(num+1,num+1+cnt,num[i]/5)-num);
if(num[i]%7==0) location[i][7]=(int)(lower_bound(num+1,num+1+cnt,num[i]/7)-num);
location[i][4]=location[location[i][2]][2];
location[i][6]=location[location[i][2]][3];
location[i][8]=location[location[location[i][2]][2]][2];
location[i][9]=location[location[i][3]][3];
}
memset(f,-1,sizeof(f));
return;
}
void Dynamic_Programming(int current,int rest)//从高位往低位枚举，从低位向高位填数
{
if(!current)//到了第0位
{
f[current][rest]=(rest==1);//第0位只还需要再乘1，此时的方案数为1
g[current][rest]=0;//后面不需要填数了，和为0
return;
}
if(f[current][rest]!=-1) return;//算过了就返回
f[current][rest]=g[current][rest]=0;
for(int i=9,_current,_rest;i>=1;i--)//枚举当前这位
{
_current=current-1;
_rest=location[rest][i];//还要除的就要除以i
if(!_rest) continue;//不能整除这一位
Dynamic_Programming(_current,_rest);
f[current][rest]=(f[current][rest]+f[_current][_rest])%mod;
g[current][rest]=(g[current][rest]+i*f[_current][_rest]*power_10[_current]+g[_current][_rest])%mod;//原来的加上这一位产生的贡献
}
return;
}
void Dynamic_Programming_0(int current,int low,int zero,int cnt0)//填到第几位，填的这些位是小于（1）还是等于（0）最大值，是否有前导零，当前零的个数
{
if(!current)
{
f0[current][low][zero][cnt0]=(cnt0>0);
g0[current][low][zero][cnt0]=0;
return;
}
if(f0[current][low][zero][cnt0]!=-1) return;
f0[current][low][zero][cnt0]=g0[current][low][zero][cnt0]=0;
for(int i=low?9:number[current],_current,_low,_zero,_cnt0;i>=0;i--)//等于的话就从该位的数开始枚举，小于的话填什么都行了
{
_current=current-1;
_low=low|(i<number[current]);//到这一位为止小于或者这一位小于或者都小于，那么得到的新值就是小于的
_zero=zero&(i==0);//之前有前导零并且这一位也是零才能继续是前导零，否则没有
_cnt0=cnt0+((!zero)&(i==0));//如果有前导零，那么该位的零的个数不变，否则这一位等于零那就是多了一个零
Dynamic_Programming_0(_current,_low,_zero,_cnt0);
f0[current][low][zero][cnt0]=(f0[current][low][zero][cnt0]+f0[_current][_low][_zero][_cnt0])%mod;
g0[current][low][zero][cnt0]=(g0[current][low][zero][cnt0]+i*f0[_current][_low][_zero][_cnt0]*power_10[_current]+g0[_current][_low][_zero][_cnt0])%mod;
}
return;
}
ll solve(int current,int low,int zero,int rest,ll pre)//当前到第几位，填的这些位小于还是等于最大值，是否有前导零，剩下还要多少乘积，当前的前缀值
{
if(!rest) return 0;//如果需要到了0，说明不能被整除，也就是累加不了答案，所以就对答案产生0的贡献
if(low&(!zero))//没有前导零并且小于
{
if(f[current][rest]==-1) Dynamic_Programming(current,rest);//没有更新过
return (pre*power_10[current]%mod*f[current][rest]+g[current][rest])%mod;
}
if(!current) return pre*(rest==1);//如果是第0位，那就返回
ll res=0;
for(int i=low?9:number[current],_current,_low,_zero,_rest;i>=(!zero);i--)//等于的话就从该位的数开始枚举，小于的话填什么都行了
{
_current=current-1;//同上
_low=low|(i<number[current]);//同上
_zero=zero&(i==0);//同上
_rest=(i==0)?rest:location[rest][i];//如果当前这位要填0，那么一定是前导零，所以还要填的位数之积不变，否则就要除以i
ll _pre=(pre*10+i)%mod;//原来的前缀十进制下左移了一位，再加上新一位的值
res+=solve(_current,_low,_zero,_rest,_pre);
}
return res;
}
ll calc(ll x)
{
int len=0;
while(x)
{
number[++len]=x%10;
x/=10;
}
if(!k)
{
memset(f0,-1,sizeof(f0));
Dynamic_Programming_0(len,0,1,0);
return g0[len][0][1][0];
}
return solve(len,0,1,(int)(lower_bound(num+1,num+1+cnt,k)-num),0);
}
int main()
{
init();
n=read();
for(int i=1;i<=n;i++)
{
l=read(),r=read(),k=read();
if(!k) printf("%lld\n",((calc(r)-calc(l-1))%mod+mod)%mod);
else if(check(k)) printf("%lld\n",((calc(r)-calc(l-1))%mod+mod)%mod);
else printf("%d\n",0);
}
return 0;
}