题目传送门:http://codeforces.com/contest/55/problem/D
官方题解:http://codeforces.com/blog/entry/1109
中文题面:number_dp_by_zky
之前做数位dp的题目,一直强调数位间的独立性
然而现在看来,不独立也是可以上数位dp的
题解直接看上面给的“中文题面”里的题解吧,zky的题解真的是超级棒(๑•̀ㅂ•́)و✧
我来说一说代码实现的三种方式:
1)像之前的代码一样,先预处理,然后查询的时候在数组上搞一搞
优点:对于多组询问特别好用
缺点:因为是预处理,所以对于有些题目可能很麻烦,甚至不能预处理
2)对于每一次询问单独dp,记录是否达到上限
优点:代码好写(不用于处理,直接写一个dp就成)
缺点:多组询问没法处理
3)对于每一次询问DFS,如果这一位没有受到任何限制就记忆化
这种方法是我在看这位神犇的代码的时候看到的:http://codeforces.com/contest/55/submission/3692033
优点:代码更好写,且对于多组询问相对友好(仔细想一想,他的查询次数应该不会劣于方法1?)
缺点:如果位数特别大(什么1e5,1e6之类的),则效果可能不太好
总的来说,我似乎爱上了第三种写法 = ̄ω ̄=
以后数位dp的题应该是首选第三种吧!
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int MOD[]={1,1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520};
int pos[2530],lcm[50][50],sta[20];
LL f[20][50][2530];
LL GCD(LL a, LL b) {return b?GCD(b,a%b):a;}
LL LCM(LL a, LL b) {return a/GCD(a,b)*b;}
LL DFS(int t, int lm, int mod, bool top) {
if (t == 0) {
return !(mod % MOD[lm]);
} else if (~f[t][lm][mod] && !top) {
return f[t][lm][mod];
} else {
LL ret = 0;
for (int i=0,ty=(top>0?sta[t]:9),tmp;i<=ty;i++) {
tmp = lcm[lm][i];
ret += DFS(t-1,tmp,(mod*10+i)%2520,top&&i==sta[t]);
}
return top?ret:f[t][lm][mod] = ret;
}
}
inline LL cal(LL lim) {
int cnt = 0;
while (lim) {
sta[++cnt] = lim % 10;
lim /= 10;
}
return DFS(cnt,1,0,1);
}
inline LL read(){
char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
int main(){
memset(f,-1,sizeof(f));
for (int i=1;i<=48;i++) {
pos[MOD[i]] = i;
}
for (int i=0;i<=48;i++) {
for (int j=0;j<=48;j++) {
lcm[i][j] = pos[LCM(MOD[i],MOD[j])];
}
}
for (int T=read();T;--T) {
LL l = read(), r = read();
printf("%I64d\n",cal(r)-cal(l-1));
}
return 0;
}