CF 55D. Beautiful numbers(数位DP)

这题，没想出来，根本没想到用最小公倍数来更新，一直想状态压缩，不过余数什么的根本存不下，看的von学长的blog，比着写了写，就是模版改改，不过状态转移构造不出，怎么着，都做不出来。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define LL __int64
 6 #define MOD 2520
 7 LL dp[31][2600][50];
 8 int index[3000];
 9 int num[31];
10 LL gcd(LL a,LL b)
11 {
12     return b == 0?a:gcd(b,a%b);
13 }
14 LL lcm(LL a,LL b)
15 {
16     return a*b/gcd(a,b);
17 }
18 LL dfs(int pos,int pre,int mod,int bound)
19 {
20     int end,tpre,tmod,i;
21     LL ans = 0;
22     if(pos == -1)
23     return pre%mod == 0;
24     if(!bound&&dp[pos][pre][index[mod]] != -1)
25     return dp[pos][pre][index[mod]];
26     end = bound ? num[pos] : 9;
27     for(i = 0;i <= end;i ++)
28     {
29         tpre = (pre*10 + i)%MOD;
30         if(i)
31         tmod = lcm(mod,i);
32         else
33         tmod = mod;
34         ans += dfs(pos-1,tpre,tmod,bound&&i == end);
35     }
36     if(!bound)
37     dp[pos][pre][index[mod]] = ans;
38     return ans;
39 }
40 LL judge(LL x)
41 {
42     int pos = 0;
43     while(x)
44     {
45         num[pos++] = x%10;
46         x = x/10;
47     }
48     return dfs(pos-1,0,1,1);
49 }
50 int main()
51 {
52     int t,i,num = 0;
53     LL x,y;
54     memset(dp,-1,sizeof(dp));
55     for(i = 1;i <= MOD;i ++)
56     {
57         if(MOD%i == 0)
58         index[i] = num++;
59     }
60     cin>>t;
61     while(t--)
62     {
63         cin>>x>>y;
64         printf("%I64d
",judge(y)-judge(x-1));
65     }
66     return 0;
67 }