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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
| 好的！你的思路非常巧妙——**套一层二分**，这样就不需要逐位构造了，直接对数值进行二分，然后用一个 `count_less_than(x)` 函数统计小于 `x` 的非常奇数个数。
这个方法更通用且更容易实现，因为：
1. 不需要逐位构造
2. 不需要先找长度
3. 可以直接用从高位到低位的DP来统计
我来给你实现完整的Python代码：
def solve():
"""
求第10^16个非常奇数
"""
TARGET = 10**16
# 预计算10^i mod 7
pow7 = [1] # 10^0 mod 7
for i in range(1, 200):
pow7.append((pow7[-1] * 10) % 7)
# 数字对应的bit
digit_bit = {1: 0, 3: 1, 5: 2, 7: 3, 9: 4}
odd_digits = [1, 3, 5, 7, 9]
from functools import lru_cache
def count_less_than(x):
"""
统计小于x的非常奇数个数
x是一个整数（大整数）
"""
if x <= 0:
return 0
s = str(x)
L = len(s)
# 先统计所有长度小于L的非常奇数
total = 0
# dp_len[len][mod7][mod3][mask][last_fixed]
# 从高位到低位的DP，用于统计固定长度的数量
def count_fixed_length(length):
"""统计长度为length的非常奇数总数"""
if length <= 0:
return 0
@lru_cache(None)
def dfs(pos, mod7, mod3, mask, last_fixed):
"""
pos: 当前要填的位置（从0开始，0表示最高位）
已经填了从0到pos-1位，当前状态为：
mod7: 已填部分对7的余数
mod3: 已填部分对3的余数
mask: 已填数字的奇偶掩码
last_fixed: 是否已经确定最低位为5（0=未确定，1=已确定）
"""
if pos == length:
# 所有位都填完了
# 条件：mod7=0, mod3=0, mask全1（所有5个奇数数字出现奇数次）
return 1 if (mod7 == 0 and mod3 == 0 and mask == 0b11111 and last_fixed == 1) else 0
# 判断当前位是否是最低位（从高位往低位，pos从0开始）
is_last = (pos == length - 1)
res = 0
for d in odd_digits:
# 如果是最低位，必须填5
if is_last:
if d != 5:
continue
new_mod7 = (mod7 + d * pow7[length - 1 - pos]) % 7
new_mod3 = (mod3 + d) % 3
new_mask = mask ^ (1 << digit_bit[d])
new_last_fixed = 1 if is_last else last_fixed
res += dfs(pos + 1, new_mod7, new_mod3, new_mask, new_last_fixed)
return res
result = dfs(0, 0, 0, 0, 0)
dfs.cache_clear()
return result
# 累加所有长度小于L的非常奇数
for length in range(1, L):
if length % 2 == 1: # 长度必须是奇数（5个奇数次数之和为奇数）
total += count_fixed_length(length)
# 现在统计长度为L且小于x的非常奇数
# 使用逐位统计的方法
@lru_cache(None)
def count_prefix(pos, mod7, mod3, mask, last_fixed, tight):
"""
统计长度为L，从pos位开始填，当前状态为...
tight: 是否受到x的限制（1表示前缀与x相同，0表示已经小于x）
"""
if pos == L:
return 1 if (mod7 == 0 and mod3 == 0 and mask == 0b11111 and last_fixed == 1) else 0
is_last = (pos == L - 1)
limit = int(s[pos]) if tight else 9
res = 0
for d in odd_digits:
if d > limit:
continue
# 如果是最低位，必须填5
if is_last and d != 5:
continue
# 如果当前是最高位且d为0（但d都是奇数，不会为0，所以没问题）
new_mod7 = (mod7 + d * pow7[L - 1 - pos]) % 7
new_mod3 = (mod3 + d) % 3
new_mask = mask ^ (1 << digit_bit[d])
new_last_fixed = 1 if is_last else last_fixed
new_tight = tight and (d == limit)
res += count_prefix(pos + 1, new_mod7, new_mod3, new_mask, new_last_fixed, new_tight)
return res
# 统计长度为L且小于x的非常奇数
total += count_prefix(0, 0, 0, 0, 0, 1)
count_prefix.cache_clear()
return total
# 二分查找
print("开始二分查找...")
lo = 0
hi = 10**100 # 足够大的上界
# 先快速扩大上界
while count_less_than(hi) < TARGET:
hi *= 10
if hi > 10**200:
break
print(f"上界确定为: 10^{len(str(hi))-1} 左右")
# 标准二分
while lo + 1 < hi:
mid = (lo + hi) // 2
cnt = count_less_than(mid)
if cnt < TARGET:
lo = mid
else:
hi = mid
# 进度提示
if (hi - lo) < 10**100:
print(f"当前范围: [{lo}, {hi}], 区间大小: {hi-lo}")
# hi就是第TARGET个非常奇数
print(f"\n答案: {hi}")
print(f"验证: 小于{hi}的非常奇数个数 = {count_less_than(hi)}")
print(f"小于{hi-1}的非常奇数个数 = {count_less_than(hi-1)}")
return hi
if __name__ == "__main__":
import time
start = time.time()
result = solve()
print(f"运行时间: {time.time() - start:.2f}秒")
**但是注意**：上面的代码虽然逻辑正确，但二分过程中每次 `count_less_than(mid)` 都会重新计算DP，而二分需要约 `log2(10^100) ≈ 333` 次调用，每次调用DP的复杂度约为 `L * 7 * 3 * 32 * 2 * 5 ≈ L * 6720`，其中L是当前数字的位数（约100位），所以总计算量约为 `333 * 100 * 6720 ≈ 2.24亿` 次操作，Python可能会比较慢。
---
## 优化版本：使用记忆化 + 预计算
我们可以**缓存**每个长度的DP结果，因为 `count_less_than(x)` 在不同长度上重复计算了很多次。
from functools import lru_cache
def solve_optimized():
TARGET = 10**16
# 预计算10^i mod 7
pow7 = [1]
for i in range(1, 250):
pow7.append((pow7[-1] * 10) % 7)
digit_bit = {1: 0, 3: 1, 5: 2, 7: 3, 9: 4}
odd_digits = [1, 3, 5, 7, 9]
# 缓存每个长度的DP结果
length_cache = {}
def get_length_count(length):
"""获取长度为length的非常奇数总数（带缓存）"""
if length in length_cache:
return length_cache[length]
if length <= 0 or length % 2 == 0:
length_cache[length] = 0
return 0
@lru_cache(None)
def dfs(pos, mod7, mod3, mask, last_fixed):
if pos == length:
return 1 if (mod7 == 0 and mod3 == 0 and mask == 0b11111 and last_fixed == 1) else 0
is_last = (pos == length - 1)
res = 0
for d in odd_digits:
if is_last and d != 5:
continue
new_mod7 = (mod7 + d * pow7[length - 1 - pos]) % 7
new_mod3 = (mod3 + d) % 3
new_mask = mask ^ (1 << digit_bit[d])
new_last_fixed = 1 if is_last else last_fixed
res += dfs(pos + 1, new_mod7, new_mod3, new_mask, new_last_fixed)
return res
result = dfs(0, 0, 0, 0, 0)
dfs.cache_clear()
length_cache[length] = result
return result
@lru_cache(maxsize=None)
def count_less_than(x):
"""统计小于x的非常奇数个数"""
if x <= 0:
return 0
s = str(x)
L = len(s)
# 统计所有长度小于L的
total = 0
for length in range(1, L):
total += get_length_count(length)
# 统计长度为L且小于x的
@lru_cache(None)
def dfs_prefix(pos, mod7, mod3, mask, last_fixed, tight):
if pos == L:
return 1 if (mod7 == 0 and mod3 == 0 and mask == 0b11111 and last_fixed == 1) else 0
is_last = (pos == L - 1)
limit = int(s[pos]) if tight else 9
res = 0
for d in odd_digits:
if d > limit:
continue
if is_last and d != 5:
continue
new_mod7 = (mod7 + d * pow7[L - 1 - pos]) % 7
new_mod3 = (mod3 + d) % 3
new_mask = mask ^ (1 << digit_bit[d])
new_last_fixed = 1 if is_last else last_fixed
new_tight = tight and (d == limit)
res += dfs_prefix(pos + 1, new_mod7, new_mod3, new_mask, new_last_fixed, new_tight)
return res
total += dfs_prefix(0, 0, 0, 0, 0, 1)
dfs_prefix.cache_clear()
return total
# 二分查找
print("开始二分查找...")
lo = 0
hi = 10**100
# 快速扩大上界
while count_less_than(hi) < TARGET:
hi *= 10
print(f"扩大上界到: 10^{len(str(hi))-1}")
print(f"上界确定: {hi}")
# 二分
step = 0
while lo + 1 < hi:
mid = (lo + hi) // 2
cnt = count_less_than(mid)
step += 1
if step % 10 == 0:
print(f"第{step}步: 范围 [{lo}, {hi}], 区间大小: {hi-lo}")
if cnt < TARGET:
lo = mid
else:
hi = mid
print(f"\n答案: {hi}")
print(f"验证: count_less_than({hi}) = {count_less_than(hi)}")
print(f"count_less_than({hi-1}) = {count_less_than(hi-1)}")
return hi
这个优化版本会缓存所有长度的DP结果，并且 `count_less_than` 也使用了 `lru_cache`，但由于x在二分中变化很大，实际上缓存命中率不高。不过长度缓存能显著提升速度。
---
## 最终建议
直接运行上面的优化版本即可。由于二分需要约300-400次 `count_less_than` 调用，每次调用会统计一个长度L的所有前缀情况，总时间复杂度大约为 `O(binary_search_steps * L * 7 * 3 * 32 * 2 * 5)`，在我的估算中应该在几分钟内能跑完。
如果还是太慢，可以考虑使用**并行化**或**C++**实现，但Python应该也能在可接受时间内完成（约5-10分钟）。
如果你想要更高效的实现，可以改用**从高位逐位构造**的方法（不需要二分），那样只需要一次 `count_less_than` 的变种，复杂度会低很多。需要我提供那个版本吗？
|
