Hdu 4507 吉哥系列故事——恨7不成妻 (数位DP)

题目链接:

  Hdu 4507 吉哥系列故事——恨7不成妻

题目描述:

  中文题面不描述。

解题思路:

  从数据范围可看出是数位DP。根据题目给的限制,如果是求满足限制的数的数目的话,就很简单了。但是这个题目是让求满足题目中限制的数的平方和。我们可以求出区间中满足题目中限制的数的数目,和这些数的和,然后从这两个东西推出这些数的平方和。
  假设现在我们已经递归出后面的x-1位满足题目限制的数的数目(num),和(sum),平方和(ssum),当前x位枚举为i,就可以推出当前节点改变为Num += num, Sum += num*i*pow(10, x) + sum, Ssum += ssum + 2*sum*i*pow(10, x) + num * i*pos(10, x) * i*pos(10, x);

 1 #include <vector>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef __int64 LL;
 9 const LL maxn = 11;
10 const LL Mod = 1000000007;
11 struct node
12 {
13     LL num, sum, ssum;
14     node (LL num=0, LL sum=0, LL ssum=0):num(num),sum(sum),ssum(ssum){}
15 };
16 node dp[25][10][10];
17 LL bit[25], p[20], v[20][10][10];
18 
19 node dfs (LL pos, LL mod, LL amod, bool flag)
20 {
21     if (pos == -1)  return node(mod&&amod, 0, 0);
22     if (!flag && v[pos][mod][amod]) return dp[pos][mod][amod];
23 
24     int len = flag ? p[pos] : 9;
25     node res, res1;
26 
27     for (int i=0; i<=len; i++)
28     {
29         if (i == 7) continue;
30         res1 = dfs (pos-1, (mod*10+i)%7, (amod+i)%7, flag&i==len);
31         LL tem = bit[pos] * i % Mod;
32         res.num = (res.num + res1.num) % Mod;
33         res.sum = (tem * res1.num % Mod + res.sum + res1.sum) % Mod;
34         res.ssum = (tem*tem%Mod*res1.num%Mod + 2*tem*res1.sum%Mod + res1.ssum + res.ssum) % Mod;
35     }
36 
37     if (!flag)
38     {
39         v[pos][mod][amod] = true;
40         dp[pos][mod][amod] = res;
41     }
42 
43     return res;
44 }
45 
46 LL solve (LL n)
47 {
48     int pos = 0;
49     while (n)
50     {
51         p[pos ++] = n % 10;
52         n /= 10;
53     }
54     return dfs (pos-1, 0, 0, true).ssum;
55 }
56 
57 int main ()
58 {
59     LL n, L, R;
60     bit[0] = 1;
61     for (int i=1; i<20; i++)
62         bit[i] = bit[i-1] * 10;
63 
64     memset (v, false, sizeof(v));
65     scanf ("%I64d", &n);
66 
67     while (n --)
68     {
69         scanf ("%I64d %I64d", &L, &R);
70         printf ("%I64d
", (solve(R) - solve(L-1)+ Mod) % Mod);
71     }
72 
73     return 0;
74 }