吉哥系列故事――恨7不成妻

题意

来源:HDU - 4507

如果一个整数符合下面3个条件之一,那么我们就说这个整数和7有关——

  1. 整数中某一位是7;
  2. 整数的每一位加起来的和是7的整数倍;
  3. 这个整数是7的整数倍;

吉哥想知道在一定区间内和7无关的数字的平方和。

分析

我们分析一个整数平方和的拆分
$A^2 = (a + b + c + d) ^ 2 = a^2 + 2 \times a \times (b + c + d) + (b + c + d)^2$

发现是可以递归计算的。

式子中需要用到数的和(sum)

而计算数的和需要用到数的个数

所以我们要维护三个值:

  1. cnt 满足条件数的个数
  2. sum 满足条件数的和
  3. squ 满足条件数的平方和

squ的计算方法上面已经给出来了,那么sum怎么计算呢?

假设枚举到第i位,那么这一位的贡献就是 val pow(10,i) cnt

val是当前数位的值,cnt是枚举到第i+1位时满足条件数的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
typedef long long ll;
const int mod = 1e9 + 7;

int num[20];
ll Pow[20];
struct P {
ll cnt, squ, sum;
P() {
cnt = -1;
squ = sum = 0;
}
P(int c, int s1, int s2) : cnt(c), sum(s1), squ(s2) {}
};
P dp[20][20][20];

P dfs(int pos, bool limit, int sum, int mul) {
if (pos == -1) {
P ret(0, 0, 0);
if (sum && mul) ret.cnt = 1;
return ret;
}
if (!limit && dp[pos][sum][mul].cnt != -1) return dp[pos][sum][mul];
int up = limit ? num[pos] : 9;
P ans(0, 0, 0);
for (int i = 0; i <= up; i++) {
if (i == 7) continue;
P temp =
dfs(pos - 1, limit && i == up, (sum + i) % 7, (mul * 10 + i) % 7);
ll A = i * Pow[pos] % mod;
ans.cnt += temp.cnt % mod;
ans.cnt %= mod;
ans.sum += (A * temp.cnt % mod + temp.sum) % mod;
ans.sum %= mod;
ans.squ +=
((A * A % mod * temp.cnt % mod + 2 * A % mod * temp.sum) % mod +
temp.squ) %
mod;
ans.squ %= mod;
}
if (!limit) dp[pos][sum][mul] = ans;
return ans;
}

P solve(ll val) {
int pos = 0;
while (val) {
num[pos++] = val % 10;
val /= 10;
}
return dfs(pos - 1, true, 0, 0);
}
int main() {
/*
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
*/
std::ios::sync_with_stdio(false);
int T;
cin >> T;
Pow[0] = 1;
for (int i = 1; i < 20; i++) {
Pow[i] = Pow[i - 1] * 10 % mod;
}
while (T--) {
ll l, r;
cin >> l >> r;
P R = solve(r);
P L = solve(l - 1);
cout << (R.squ - L.squ + mod) % mod << endl;
}
}
Thank you for your support!