HDOJ 6156

发表于 |

题目

$f(n,k):=k\times[n为k进制下的回文数]+[n不是k进制下的回文数]$

求$\sum_{i=L}^{R} \sum_{j=l}^{r}f(i,j)$

数据范围

$1\leq L,R\leq 10^9 \quad 2\leq l,r\leq 36$

做法

枚举进制$K$,数位DP或者直接$O(log_K)$地算出$[L, R]$有多少$K$进制下的回文数。

代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int digits[35], len;
// int tmpDigits[35];
// ll mem[39][39][40][2];
/*
ll dfs(int k, int start, int pos, int s, bool limit)
{
  if (pos == -1) {
    return s;
  }
  if (!limit && mem[k][start][pos][s] != -1) {
    return mem[k][start][pos][s];
  }
  int maxi = limit ? digits[pos] : k - 1;
  ll ans = 0;
  for (int i = 0; i <= maxi; ++i) {
    tmpDigits[pos] = i;
    if (pos == start && i == 0) {
      ans += dfs(k, start - 1, pos - 1, s, limit && i == maxi);
    } else {
      if (s == 1 && pos <= (start - 1) / 2) {
        ans += dfs(k, start, pos - 1, tmpDigits[start - pos] == i, limit && i == maxi);
      } else {
        ans += dfs(k, start, pos - 1, s, limit && i == maxi);
      }
    }
  }
  if (!limit) mem[k][start][pos][s] = ans;
  return ans;
}
ll solve(int n, int k)
{
  len = 0;
  while (n) {
    digits[len++] = n % k;
    n /= k;
  }
  return dfs(k, len - 1, len - 1, 1, true);
}
*/
ll solve2(int n, int k)
{
  len = 0;
  while (n) {
    digits[len++] = n % k;
    n /= k;
  }
  ll ret = 1;
  for (int i = len / 2, j = len - 1 - i; i < len; ++i, --j) {
    if (digits[i] != digits[j]) {
      if (digits[i] > digits[j]) --ret;
      break;
    }
  }
  ll tmpNum = 0;
  for (int i = len - 1; i >= len / 2; --i) {
    tmpNum = tmpNum * k + digits[i];
  }
  ret += tmpNum;
  tmpNum = 0;
  for (int i = len / 2; i > 0; --i) {
    tmpNum = tmpNum * k + (k - 1);
  }
  ret += tmpNum;
  return ret;
}
int main()
{
  // memset(mem, -1, sizeof mem);
  int T; scanf("%d", &T);
  for (int ca = 1; ca <= T; ++ca) {
    int L, R, l, r;
    scanf("%d%d%d%d", &L, &R, &l, &r);
    ll ans = 0;
    for (int i = l; i <= r; ++i) {
      // ll tmpN = solve(R, i);
      ll tmpN = solve2(R, i);
      ans += tmpN * (i - 1) + R;
      // tmpN = solve(L - 1, i);
      tmpN = solve2(L - 1, i);
      ans -= tmpN * (i - 1) + L - 1;
    }
    printf("Case #%d: %I64d\n", ca, ans);
  }
  return 0;
}