时间紧张,就不讲那么详细了。
之前一直被深搜代码误解,以为数位dp 其实就是记忆化深搜...(虽说爆搜确实很舒服而且还好想)
但是后来发现数位dp 的标准格式其实是 预处理 + dp ......
数位dp 的介绍
数位 dp 其实就是让你处理出某一区间范围内满足条件的数的个数,但是一般这个区间范围都是令人绝望的大...比如 1e9 都算良心了,常规的都是 1e18 甚至是 1e10n (n 一般为 3 或 5)次这样的...
数位dp 的一般解法
那么我们知道肯定不能在区间内一个个去判断数字是否满足条件,于是我们就引入了 数位处理 的概念:
处理不多于 i 位的数中 (如 i = 10、100、1000、1e4、1e5)有多少数满足条件,dp[i] 就表示小于等于 10i 的数中,有多少数满足条件。
但大部分题目与数字本身有一定关系(如不能出现某些特定数字或者必须出现某些式子之类的),那么我们就要多加一维(或者多维)来进行转移,
那么 dp[i][j] 就表示第 i 位为 j 的,满足条件的数字有多少个。
接下来我们再按位对于 区间端点 进行处理。这里为什么是对区间端点处理?(不是显然么?不然你枚举区间内每个数?)
回想之前的操作,我们可以用预处理出的信息来计算出 1 ~ 某个数 的范围内有多少数满足条件,又因为我们计算出的是前缀信息,满足区间可加(减)性,
于是我们可以计算出 $1 到 L-1$ 和 $1 到 R$ ( [L,R] 为要计算的满足条件的数字所处的区间范围 )这两个区间内有多少数满足条件,然后减一减答案就出来了。
具体怎么实现?我们一般考虑在当前处理的位 (i) 上固定一个数字(但这个数要小于 n 的第 i 位),然后易知,后面的数字我们随便填都行,
弄完后我们把 n 的第 i 位当做填上去了(或者是记录下来和下一位作比较,这要看题目而定),迭代处理接下来的步骤。
然而数位dp 说是说 dp ,有的时候 dp 数组是预处理出来累加答案的...优秀!
相信这些东西看完也没多大用处(毕竟实践出真知嘛,大家都是做题做着做着才明白理论都在讲啥的么...)
数位dp 基础入门
先来三道蓝题(真的没有颜色更浅的题了啊QwQ)
- 洛谷 P2657 [SCOI2009]windy数
- 洛谷 P2518 [HAOI2010]计数
- 洛谷 P3413 SAC#1 - 萌数
相信你们都看到了题目前的标签...(瓦特?省选?FAQ!) 。。。但是骚年不要弃疗啊...你做着做着就发现没这么恐怖啦!
1.洛谷 P2657 [SCOI2009]windy数
题目描述
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,
在A和B之间,包括A和B,总共有多少个windy数?
输入输出格式
输入格式:
包含两个整数,A B。
输出格式:
一个整数
分析
不难,预处理一下 i 位数的范围内多少数字满足相差大于 1 就好了,然后常规 solv 也很难解释清楚,具体得看代码。
代码
//by Judge
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int M=;
ll f[M][][],d[M],l,r,ans;
inline bool get(int x){ return x> || x<-; } //判断是否满足条件
inline void prep(){ //预处理,不难看懂?
for(int i=,x,y,z;i<=;++i) for(x=;x<=;++x)
for(y=;y<=;++y) if(get(x-y)){ //如果满足条件就进行枚举
for(z=;z<=;++z) if(get(y-z)) //如果满足条件就累加
f[i][x][y]+=f[i-][y][z];
if(i==) ++f[i][x][y]; //特殊情况,i==2 无法累加,直接手动+1
}
}
inline ll solv(int n,ll res=,int len=){
if(n<) return n; //10以内的数必然都满足,直接返回,否则进行数的分解
while(n) d[++len]=n%,n/=; int las=-1; //las是上一位数,具体看下面才清楚
for(int i=,j,k;i<len;++i) for(j=;j<=;++j) //枚举状态(由于位数小于当前 n 的数是不受限制的,可以直接累加),至于位数等于 len 的我们另外处理
for(k=;k<=;++k) res+=f[i][j][k];
res+=; bool flag=; //答案+9(其实就是 1~9 这 9 个数字),然后立一个 flag
for(int i=len,j,k;i>;--i){ //自高向低位处理
for(j=;j<d[i];++j) if((i^len || j) && get(j-las)) //最高位不为零,且 j 和上一位数字相差>1 则开始枚举
for(k=;k<=;++k) res+=f[i][j][k]; //满足条件则累加答案
if(!get(las-d[i])){ flag=; break; } las=d[i]; //如果处理到当前位已经不满足条件了 否则 las 记录当前数,为下一次计算准备
}
if(flag) for(int j=;j<=d[];++j) //如果 flag 还在,说明前面的 2~len 的数都满足条件,那么最低位累加答案
if(get(j-las)) ++res;
return res;
}
signed main(){
cin>>l>>r,prep(); //预处理
ans=solv(r)-solv(l-); //计算答案
printf("%lld\n",ans);
return ;
}
相信有了第一道题的入门,后面就没有那么麻烦了...于是乎~后面我代码里面的注释就不那么啰嗦了(反正你这么聪明一定看得懂的)
2.洛谷 P2518 [HAOI2010]计数
题目描述
你有一组非零数字(不一定唯一),你可以在其中插入任意个0,这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。
现在给定一个数,问在这个数之前有多少个数。(注意这个数不会有前导0).
输入输出格式
输入格式:
只有1行,为1个整数n.
输出格式:
只有整数,表示N之前出现的数的个数。
分析
这道题其实没这么难!预处理组合数就行!
然而想想自己做的时候傻* 了... 在放置数字的时候直接排列(也就是用阶乘 乘上去),完了还奇怪怎么答案这么大
注意!相同的数字调换了位置还是算一种方案!(对自己说的吧...)
代码
//by Judge
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
char s[];
ll len,d[],num[],C[][];
inline void prep(){ //预处理组合数
for(int i=;i<=;++i) C[i][]=;
for(int i=,j;i<=;++i) for(j=;j<=;++j)
C[i][j]=C[i-][j-]+C[i-][j];
}
inline ll solv(){
ll ans=,tot,tmp;
for(int i=,j,k;i<=len;++i){
for(j=;j<d[i];++j) if(num[j]){
--num[j],tmp=,tot=len-i; //先将这一位填上
for(k=;k<=;++k) tmp*=C[tot][num[k]],tot-=num[k]; //然后累乘方案数(tot 个空位里面放 num[k] 个数字)
ans+=tmp,++num[j]; //累加答案,然后把填上的数字拿回来
} --num[d[i]]; //当前位的数字减掉,做下一位
} return ans;
}
signed main(){
scanf("%s",s+),prep(),len=strlen(s+); //分解数字
for(int i=;i<=len;++i) ++num[d[i]=s[i]-'']; //处理每种数字多少个
printf("%lld\n",solv()); return ;
}
题目背景
本题由世界上最蒟蒻最辣鸡最撒比的SOL提供。
寂月城网站是完美信息教室的官网。地址:http://191.101.11.174/mgzd 。
题目描述
辣鸡蒟蒻SOL是一个傻逼,他居然觉得数很萌!
好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为2的回文子串”的数是萌的——也就是说,101是萌的,因为101本身就是一个回文数;110是萌的,因为包含回文子串11;但是102不是萌的,1201也不是萌的。
现在SOL想知道从l到r的所有整数中有多少个萌数。
由于答案可能很大,所以只需要输出答案对1000000007(10^9+7)的余数。
输入输出格式
输入格式:
输入包含仅1行,包含两个整数:l、r。
输出格式:
输出仅1行,包含一个整数,即为答案。
分析
我们可以从题目中分析出,如果一个数字中存在长度>=2回文子串,那么必然存在长度为 2 或 3 的回文子串(我们可以把回文子串两头反复去掉,直至长度为 2 或 3)
接着我们考虑计算满足的数的个数太麻烦了,于是就可以计算不满足的数的个数,然后和 tot (总共有多少数)减一减,答案就出来了。
然后我们在设计一个三维的dp状态(记录第 i 位,首位是 j ,次位是 k 的数字有多少个)就可以开始状态转移了。
代码
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=;
const ll mod=1e9+;
ll f[N][][],ans;
string l,r;
inline void prep(){ //预处理就不解释了
for(int i=,x,y,z;i<=;++i) for(x=;x<=;++x)
for(y=;y<=;++y) if(x!=y){
for(z=;z<=;++z) if(x!=z && y!=z)
f[i][x][y]+=f[i-][y][z];
if(i==) ++f[i][x][y]; f[i][x][y]%=mod;
}
}
inline ll solv(string s){
int len=s.length(),X=-,Y=-; //这里有点特殊,要记录前两个数字
ll tot=,ans=; bool flag=;
for(int i=;i<len;++i) tot=(tot*+s[i]-'')%mod;
for(int i=,x,y;i<len;++i) for(x=;x<=;++x)
for(y=;y<=;++y) ans=(ans+f[i][x][y])%mod;
if(len>) ans+=;
for(int i=len,j,k;i>;--i){
int now=s[len-i]-'';
for(j=;j<now;++j) if((i!=len || j!=) && X!=j && Y!=j )
for(k=;k<=;++k) if(j!=k && k!=X) ans=(ans+f[i][j][k])%mod;
if(now==X || now==Y) { flag=; break; } Y=X,X=now; //和 windy 数类似?
}
if(flag) for(int j=;j<=s[len-]-'';++j)
if(j!=Y && j!=X) ans=(ans+)%mod;
return (tot++mod-ans)%mod;
}
int main(){
prep(),cin>>l>>r;
ans=(solv(r)-solv(l)+mod)%mod;
for(int i=;i<=l.length()-;++i) //数字太长有两种解决方法,一是暴力减(根据当前位不够就向高位借的原则),这里是暴力算当前数是否满足,满足就累加
if(l[i]==l[i-] || l[i-]==l[i+]){
ans=(ans+)%mod; break;
}
printf("%lld\n",ans);
}
基础入门是讲完了,这里还有一堆题目呢,感动伐?(唔...别打脸)
loj 第三章:数位动态规划
- #10163 「一本通 5.3 例 1」Amount of Degrees
- #10164 「一本通 5.3 例 2」数字游戏
- #10165 「一本通 5.3 例 3」Windy 数(emmm...)
- #10166 「一本通 5.3 练习 1」数字游戏
- #10167 「一本通 5.3 练习 2」不要 62
- #10168 「一本通 5.3 练习 3」恨 7 不成妻
- #10169 「一本通 5.3 练习 4」数字计数
做了这些题目之后你会发现被我坑了(明明这些简单一点嘛 (╯‵□′)╯︵┻━┻ )...
emmm...但是啊...你在切题的同时有没有点成就感咧?(强行解释)
数位dp 提高训练
就放两道题目吧...
- 洛谷 P4317 花神的数论题
- 洛谷 P4124 [CQOI2016]手机号码
省选 emmm...(唔...别打脸)
1.洛谷 P4317 花神的数论题
题目背景
众所周知,花神多年来凭借无边的神力狂虐各大 OJ、OI、CF、TC …… 当然也包括 CH 啦。
题目描述
话说花神这天又来讲课了。课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了。 花神的题目是这样的:设 \text{sum}(i)sum(i)表示 ii 的二进制表示中 11 的个数。给出一个正整数 NN ,花神要问你 $ \prod_{i=1}^{N}\text{sum}(i)∏i=1Nsum(i)$ ,也就是 $\text{sum}(1)\sim\text{sum}(N)sum(1)∼sum(N)$的乘积。
输入输出格式
输入格式:
一个正整数 N。
输出格式:
一个数,答案模 10000007 的值。
分析
emmmm...算 sum[1~n] 的乘积。其实还是蛮常规的(有一道题还是加强版咧),
数字拆分的时候我们拆成二进制,然后常规的做,每次往 当前处理的第 i 位后面 i-1 个位子里面塞 1 就好了,
然后计算塞多少个 1 分别的方案数,最后快速幂一下累乘进答案。
做的时候居然纠结了半天的逆元卢卡斯什么的预处理,502 暴力递推组合是就好了啊! 看代码吧!
代码
// luogu-judger-enable-o2
//by Judge
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int M=;
const ll mod=1e7+;
ll n,len,cnt,ans=;
ll C[M][M],d[M],num[M];
inline void prep(){ //预处理组合数模板?
for(int i=;i<=;++i) C[i][]=;
for(int i=,j;i<=;++i) for(j=;j<=;++j)
C[i][j]=C[i-][j]+C[i-][j-];
}
inline ll quick_pow(ll x,ll p,ll ans=){ //快速幂模板?
while(p){
if(p&) ans=ans*x%mod;
x=x*x%mod, p>>=;
} return ans;
}
signed main(){
cin>>n,prep();
while(n) d[++len]=n&,n>>=;//转化二进制
for(ll i=len,j;i;--i) if(d[i]){
for(j=;j<i;++j) //组合数随便乱艹
num[cnt+j]+=C[i-][j];
++num[++cnt];
}
for(ll i=;i<=len;++i) //直接累乘
ans=ans*quick_pow(i,num[i])%mod;
cout<<ans<<endl; return ;
}
2. 洛谷 P4124 [CQOI2016]手机号码
题目描述
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个:号码中要出现至少 33 个相邻的相同数字;号码中不能同时出现 88 和 44。号码必须同时包含两个特征才满足条件。满足条件的号码例如:13000988721、23333333333、14444101000。而不满足条件的号码例如:1015400080、10010012022。
手机号码一定是 11 位数,前不含前导的 00。工具接收两个数 LL 和 RR,自动统计出 [L,R][L,R] 区间内所有满足条件的号码数量。LL 和 RR 也是 1111 位的手机号码。
输入输出格式
输入格式:
输入文件内容只有一行,为空格分隔的 22 个正整数 L,RL,R。
输出格式:
输出文件内容只有一行,为 11 个整数,表示满足条件的手机号数量。
分析
5维状态直接艹!...第一维记位数,第二维记是哪个数字,第三维记前面有几个相同的情况,第四维记 8 出现过没,第五维记 4 出现过没。
代码
//by Judge
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll L,R,d[],f[][][][][]; // F[ i,j,k,et,fr] 表示第 i 位,前面有 k 个相同,8 是否出现过, 4是否出现过
inline void prep(){ //预处理 dp 数组
for(int i=,j,c,et,fr,w;i<=;++i) for(j=;j<=;++j)
for(c=;c<=;++c) for(et=;et<=;++et) for(fr=;fr<=;++fr){
ll &t=f[i][j][c][et][fr]; if(!i) t=(c==?:);
else for(w=;w<=;++w) t+=f[i-][w][c==?:w==j?c+:][et||(w==)][fr||(w==)];
if(et && fr) t=;
}
}
inline ll solv(ll n){
ll len=,ans=,c=,et=,fr=;
while(n) d[++len]=n%,n/=; //分解数字
if(len<) return ; d[len+]=-; //特判 L=1e11 的情况
for(int i=len,j;i;--i){ //暴力枚举转移
for(j=;j<d[i];++j) ans+=f[i-][j][c==?:d[i+]==j?c+:][(j==)||et][(j==)||fr];
c=(c==?:d[i]==d[i+]?c+:),et|=d[i]==;fr|=d[i]==; if(et && fr) break;
} return ans-f[][][][][]+f[][d[]][c][et][fr];;
}
signed main(){ prep(),scanf("%lld%lld",&L,&R),printf("%lld\n",solv(R)-solv(L-)); return ; } //一行主函数
再来几道题目:
- 洛谷 P4127 [AHOI2009]同类分布
- 洛谷 P2606 [ZJOI2010]排列计数
- 洛谷 P3281 [SCOI2013]数数
- 洛谷 P3286 [SCOI2014]方伯伯的商场之旅
(就四道题,还有我没做过的... 0.0)
代码如下:
P4127:(...代码很短,思路很绕)
//by Judge
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
ll f[][][][],d[],l,r; //位数,整个数字%sum,各位数字的和%sum,是否达到当前位上界
inline ll solv(ll n){
ll len=,ans=,tmp;
while(n) d[++len]=n%,n/=;
for(int sum=,i,s,m,c,k;sum<=len*;++sum){
memset(f,,sizeof(f)), f[len+][][][]=;
for(i=len;i;--i) for(s=;s<=sum;++s)
for(m=;m<sum;++m) for(c=;c<=;++c){
tmp=f[i+][s][m][c]; if(!tmp) continue;
for(k=;k<=(c?d[i]:) && s+k<=sum;++k)
f[i][s+k][(m*+k)%sum][c&(k==d[i])]+=tmp;
} ans+=f[][sum][][]+f[][sum][][];
} return ans;
}
signed main(){
scanf("%lld%lld",&l,&r);
printf("%lld\n",solv(r)-solv(l-));
return ;
}
P3281:(详情看这里)
//by Judge
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define int long long
using namespace std;
const int M=1e5+;
const ll mod=;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
ll B,len,ans,d[M],f[M]={},sum[M]={},pre[M],sub[M],dp[M][];
inline void prep(){ for(int i=,j;i<=1e5;++i) f[i]=f[i-]*B%mod,sum[i]=(sum[i-]+f[i])%mod; }
inline ll solv(){
ll ans=pre[len+]=;
for(int i=;i<=len;++i) sub[i]=(d[i]*f[i-]%mod+sub[i-])%mod;
for(int i=len;i>=;--i) pre[i]=(pre[i+]*B%mod+d[i])%mod;
for(int i=;i<=len;++i){ //各种恶心...
dp[i][]=(dp[i-][]*B%mod+B*(B-)/%mod*f[i-]%mod*sum[i-]%mod)%mod;
dp[i][]=(dp[i-][]*d[i]%mod+d[i]*(d[i]-)/%mod*f[i-]%mod*sum[i-]%mod)%mod;
dp[i][]=(dp[i][]+dp[i-][]+d[i]*(sub[i-]+)%mod*sum[i-]%mod)%mod;
ans=(ans+max(0ll,pre[i+]-)*dp[i][]%mod+dp[i][])%mod;
} return ans;
}
signed main(){
B=read(),len=read(),prep();
for(int i=len;i;--i) d[i]=read();
for(int i=;i<=len;++i)
if(d[i]){ --d[i]; break; }
else d[i]=B-;
if(!d[len]) --len;
ans=-solv(), len=read();
for(int i=len;i;--i) d[i]=read();
ans+=solv(),printf("%lld\n",(ans%mod+mod)%mod); return ;
}
P2606:假题,不用做(求 n 点小根堆方案数)
//by Judge
#include<cstdio>
#include<iostream>
#define fp(i,a,b) for(int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(int i=(a),I=(b)-1;i>I;--i)
#define ll long long
using namespace std;
const int M=1e6+;
ll n,mod,s[M],ans=,inv[M];
int main(){ scanf("%lld%lld",&n,&mod);
inv[]=inv[]=; fp(i,,n) s[i]=;
fp(i,,n) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
fd(i,n,) s[i>>]+=s[i];
fp(i,,n) ans=ans*i%mod*inv[s[i]]%mod;
return !printf("%lld\n",ans);
}
P3286:(不是很懂,瞎抄的)
//by Judge
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
const int M=;
ll L,R,K,num[M],f[M][];
ll dfs1(ll n,ll s,bool lim){
if(!n) return s;
if(!lim && f[n][s]>=) return f[n][s];
ll res=,k=lim?num[n]:K-;
for(ll i=;i<=k;++i)
res+=dfs1(n-,s+i*(n-),lim&&(num[n]==i));
if(!lim) f[n][s]=res; return res;
}
ll dfs2(ll n,ll s,ll m,ll lim){
if(s<) return ; if(!n) return s;
if(!lim && f[n][s]>=) return f[n][s];
ll res=,k=lim?num[n]:K-;
for(ll i=;i<=k;++i)
if(n>=m) res+=dfs2(n-,s+i,m,lim&(num[n]==i));
else res+=dfs2(n-,s-i,m,lim&(num[n]==i));
if(!lim) f[n][s]=res; return res;
}
inline ll calc(ll n){
ll len=;
memset(f,-,sizeof(f));
while(n) num[++len]=n%K,n/=K;
ll res=dfs1(len,,);
for(ll i=;i<=len;++i)
memset(f,-,sizeof(f)),
res-=dfs2(len,,i,);
return res;
}
signed main(){
cin>>L>>R>>K, cout<<calc(R)-calc(L-)<<endl; return ;
}
然后再来一道比较有挑战的?
题目就是让你求 l~r 之间有多少个数是能整除自己各位上的数(排除 0 )
然后我们一看就知道数位 dp ,但是状态很难设计啊 QWQ
我们可以发现所有数位的 lcm 最大为 2520 (就是 1~ 9 的 lcm 嘛)
然后我们再看就能发现某个数模 2520 下如果能整除 它所有数位的 lcm 那么它就是满足条件的数
也就是说 一个数模其所有数位的 lcm 的结果 和 模 2520 后再去模这个 lcm 的结果 是相同的
为什么?什么为什么,因为一个数所有数位的 lcm 必然是 2520 的因子啊
那么我们考虑令 f[i][j][k] 表示还剩 i 位没有处理,当前的数模 2520 为 j,当前所有数位的 lcm 为 k 的方案数,这样状态就设计出来了
然后就是代码了:(由于一开始不会抄的题解,所以写的是 dfs ,经过几小时奋斗终于写好了自己熟悉的版本——非dfs,于是就放上来了 QVQ )
//by Judge
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define fp(i,a,b) for(int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(int i=(a),I=(b)-1;i>I;--i)
#define ll long long
using namespace std;
const int mod=;
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[<<],*p1=buf,*p2=buf;
inline ll read(){ ll x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
} char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(ll x,char chr='\n'){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]=chr;
} int tot,id[mod+],val[],d[];
ll f[][mod+][];
int GCD(int a,int b) { return b?GCD(b,a%b):a; }
int LCM(int a,int b) { return a/GCD(a,b)*b; }
void prep() {
fp(i,,mod) if(!(mod%i)) id[i]=++tot,val[tot]=i;
fp(i,,tot) fp(j,,mod/val[i]) f[][val[i]*j][i]=;
fp(i,,) fp(j,,mod) fp(k,,tot) fp(d,,)
f[i][j][k]+=f[i-][(j*+d)%mod][id[d?LCM(val[k],d):val[k]]];
}
inline ll solv(ll x){
int len=; ll ans=,Val=,Lcm=;
for(;x;x/=) d[++len]=x%;
fd(i,len,){
fp(j,,d[i]-) ans+=f[i-][(Val*+j)%mod][id[j?LCM(Lcm,j):Lcm]];
Val=(Val*+d[i])%mod,Lcm=d[i]?LCM(Lcm,d[i]):Lcm;
} return ans+!(Val%Lcm);
}
int main(){ prep(); ll T=read(),l,r;
fp(kkk,,T) l=read(),r=read(),
print(solv(r)-solv(l-));
return Ot(),;
}
(累死了...写了两个多钟头...我还是太弱了)