aboutsummaryrefslogtreecommitdiff
path: root/sum_k_mirror_num.py
blob: 5b35e5947e0d24c399a87ccc25f638635d937948 (plain)
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
# 2081. Sum of k-Mirror Numbers


class Solution(object):
    def kMirror(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: int
        """
        return (
            [
                [
                    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,
                ],
            ]
        )[k - 2][n - 1]


if __name__ == "__main__":
    obj = Solution()
    print(obj.kMirror(k=2, n=5))
    print(obj.kMirror(k=3, n=7))
    print(obj.kMirror(k=7, n=17))