-
Notifications
You must be signed in to change notification settings - Fork 522
/
d.go
93 lines (78 loc) · 3.74 KB
/
d.go
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
package main
import (
"fmt"
"strconv"
)
/* 打表
由于输入范围很小,我们可以直接把所有结果计算出来(这一共有 $8\cdot 30=240$ 个)。
从小到大构造 $10$ 镜像数字,构造方法如下:
- 对于 [10^i,10^{i+1}) 范围内的每个数,将除了末尾数位的其余数位反转并拼到原数字末尾,这样可以得到所有长为 $2i+1$ 的 $10$ 镜像数字;
- 对于 [10^i,10^{i+1}) 范围内的每个数,将所有数位反转并拼到原数字末尾,这样可以得到所有长为 $2i+2$ 的 $10$ 镜像数字。
对每个 $10$ 镜像数字判断其是否为 $k=[2,9]$ 进制数字,当得到所有 $30$ 个 $k$ 进制数字时,结束打表。
注:这最多需要枚举到 $644545$(对应的 $10$ 镜像数字为 $64454545446$)
*/
func main() {
const lim = 30
const maxK = 9
const doneMask = 1<<(maxK+1) - 1 ^ 3
ans := [maxK + 1][]int{}
done := 0
check := func(s []byte) {
num, _ := strconv.Atoi(string(s))
next:
for k := 2; k <= maxK; k++ {
if done>>k&1 == 0 {
t := strconv.FormatInt(int64(num), k)
for i, n := 0, len(t); i < n/2; i++ { // 判断 num 是否为 k 进制数字
if t[i] != t[n-1-i] {
continue next
}
}
ans[k] = append(ans[k], num)
if len(ans[k]) == lim {
done |= 1 << k
}
}
}
}
for base := 1; done != doneMask; base *= 10 {
for i := base; i < base*10 && done != doneMask; i++ {
s := []byte(strconv.Itoa(i))
n := len(s)
for j := n - 2; j >= 0; j-- {
s = append(s, s[j])
}
check(s)
}
for i := base; i < base*10 && done != doneMask; i++ {
s := []byte(strconv.Itoa(i))
n := len(s)
for j := n - 1; j >= 0; j-- {
s = append(s, s[j])
}
check(s)
}
}
for k := 2; k <= maxK; k++ {
for i := 1; i < lim; i++ {
ans[k][i] += ans[k][i-1] // 计算前缀和
}
fmt.Printf("%#v,\n", ans[k])
}
}
// github.com/EndlessCheng/codeforces-go
var ans = [10][30]int64{
{},
{},
{1, 4, 9, 16, 25, 58, 157, 470, 1055, 1772, 9219, 18228, 33579, 65802, 105795, 159030, 212865, 286602, 872187, 2630758, 4565149, 6544940, 9674153, 14745858, 20005383, 25846868, 39347399, 759196316, 1669569335, 2609044274},
{1, 3, 7, 15, 136, 287, 499, 741, 1225, 1881, 2638, 31730, 80614, 155261, 230718, 306985, 399914, 493653, 1342501, 2863752, 5849644, 9871848, 14090972, 18342496, 22630320, 28367695, 36243482, 44192979, 71904751, 155059889},
{1, 3, 6, 11, 66, 439, 832, 1498, 2285, 3224, 11221, 64456, 119711, 175366, 233041, 739646, 2540727, 4755849, 8582132, 12448815, 17500320, 22726545, 27986070, 33283995, 38898160, 44577925, 98400760, 721411086, 1676067545, 53393239260},
{1, 3, 6, 10, 16, 104, 356, 638, 1264, 1940, 3161, 18912, 37793, 10125794, 20526195, 48237967, 78560270, 126193944, 192171900, 1000828708, 1832161846, 2664029984, 3500161622, 4336343260, 6849225412, 9446112364, 12339666346, 19101218022, 31215959143, 43401017264},
{1, 3, 6, 10, 15, 22, 77, 188, 329, 520, 863, 1297, 2074, 2942, 4383, 12050, 19827, 41849, 81742, 156389, 325250, 1134058, 2043967, 3911648, 7009551, 11241875, 15507499, 19806423, 24322577, 28888231},
{1, 3, 6, 10, 15, 21, 29, 150, 321, 563, 855, 17416, 83072, 2220384, 6822448, 13420404, 20379000, 29849749, 91104965, 321578997, 788407661, 1273902245, 1912731081, 2570225837, 3428700695, 29128200347, 69258903451, 115121130305, 176576075721, 241030621167},
{1, 3, 6, 10, 15, 21, 28, 37, 158, 450, 783, 1156, 1570, 2155, 5818, 14596, 27727, 41058, 67520, 94182, 124285, 154588, 362290, 991116, 1651182, 3148123, 5083514, 7054305, 11253219, 66619574},
{1, 3, 6, 10, 15, 21, 28, 36, 227, 509, 882, 1346, 1901, 2547, 3203, 10089, 35841, 63313, 105637, 156242, 782868, 2323319, 4036490, 5757761, 7586042, 9463823, 11349704, 13750746, 16185088, 18627530},
}
func kMirror(k, n int) int64 {
return ans[k][n-1]
}