162. 十六进制数(Hexadecimal Numbers)
在十六进制数系统中，数字使用 16 个不同的数码表示：
$$0,1,2,3,4,5,6,7,8,9,\mathrm A,\mathrm B,\mathrm C,\mathrm D,\mathrm E,\mathrm F.$$十六进制数 \(\mathrm{AF}\) 在十进制中等于 \(10\times16+15=175\)。
在 3 位十六进制数 \(10\mathrm A\)、\(1\mathrm A0\)、\(\mathrm A10\) 和 \(\mathrm A01\) 中，数码 \(0\)、\(1\) 和 \(\mathrm A\) 全部出现。与十进制数的写法一样，我们书写十六进制数时没有前导零。
问：最多十六位的十六进制数中，有多少个数同时包含数码 \(0\)、\(1\) 和 \(\mathrm A\) 至少各一次？答案以十六进制数形式给出。
（A, B, C, D, E 和 F 使用大写，不加任何标记十六进制的前缀或后缀，不加前导零。例如 1A3F，而不是 1a3f、0x1a3f、$1A3F、#1A3F 或 0000001A3F）
分析：对每个长度 \(k\)（\(1\le k\le16\)），用容斥原理计算同时包含 \(0,1,\mathrm A\) 的 \(k\) 位十六进制数个数。首位不能为 0（15 种选择），其余位各 16 种。对不含某数码的集合用容斥求和。
一、数学背景
设 \(D=\{0,1,\dots,9,\mathrm A,\dots,\mathrm F\}\)（16 个数码），\(D_1=D\setminus\{0\}\)（15 个，作首位数码）。
对长度为 \(k\) 的十六进制数，首位选自 \(D_1\)，后 \(k-1\) 位选自 \(D\)。全集大小：
定义三个"不含"集合： - \(U_0\)：不含数码 0 - \(U_1\)：不含数码 1 - \(U_A\)：不含数码 \(\mathrm A\)
目标计数为 \(|\Omega| - |U_0\cup U_1\cup U_A|\)。由容斥原理：
逐项计算（首位限制 \(D_1\) 与其余位限制 \(D\) 不同）：
| 集合 | 首位选择数 | 其余位选择数 | 大小 |
|---|---|---|---|
| \(U_0\) | \(15\) | \(15^{k-1}\) | \(15^k\) |
| \(U_1\) | \(14\) | \(15^{k-1}\) | \(14\cdot15^{k-1}\) |
| \(U_A\) | \(14\) | \(15^{k-1}\) | \(14\cdot15^{k-1}\) |
| \(U_0\cap U_1\) | \(14\) | \(14^{k-1}\) | \(14^k\) |
| \(U_0\cap U_A\) | \(14\) | \(14^{k-1}\) | \(14^k\) |
| \(U_1\cap U_A\) | \(13\) | \(14^{k-1}\) | \(13\cdot14^{k-1}\) |
| \(U_0\cap U_1\cap U_A\) | \(13\) | \(13^{k-1}\) | \(13^k\) |
代入容斥公式得 \(N_k\) 通项：
其中 \(28\cdot15^{k-1} = 2\cdot14\cdot15^{k-1}\) 来自 \(U_1\) 和 \(U_A\) 两项之和。
验证 \(k=3\) 时 \(N_3=4\)，对应题面给出的四个三数码（10A、1A0、A10、A01），正确。
二、算法设计
对 \(k=1\) 到 \(16\) 求和 \(\sum N_k\)，将结果用 Python 格式化为大写十六进制数输出。所有运算使用 Python 内置整数（无限精度），可直接计算 \(16^{16}\) 以下的幂。
三、复杂度分析
仅需 16 次迭代的简单算术，时间复杂度 \(O(1)\)，远小于 60 秒限制。
四、代码实现与说明
"""
Project Euler Problem 162: Hexadecimal Numbers
Count hexadecimal numbers with at most 16 digits (no leading zeros)
that contain digits 0, 1, and A each at least once.
Output the answer as a hexadecimal number (uppercase, no prefix).
"""
def count_k(k: int) -> int:
"""Return the number of k-digit hex numbers containing 0, 1, A at least once."""
if k < 1:
return 0
return (
15 * 16 ** (k - 1)
- 15 ** k
- 28 * 15 ** (k - 1)
+ 2 * 14 ** k
+ 13 * 14 ** (k - 1)
- 13 ** k
)
def solve() -> int:
"""Sum counts for lengths 1 through 16 and return the total."""
total = 0
for k in range(1, 17):
total += count_k(k)
return total
if __name__ == "__main__":
result = solve()
print(f"{result:X}")
代码说明：
count_k
- 参数 \(k\) 为位数。返回 \(k\) 位十六进制数中同时包含 0、1、A 的个数。
- 若 \(k<1\) 返回 0（无意义输入保护）。
- 返回表达式为容斥原理推导的通项公式 \(N_k\)：
- \(15\cdot16^{k-1}\)：全集 \(|\Omega|\)
- \(-15^k\)：减去不含 0 的集合
- \(-28\cdot15^{k-1}\)：减去不含 1 和不含 A 的两个集合
- \(+2\cdot14^k\)：加回 \((0,1)\) 和 \((0,A)\) 的交集
- \(+13\cdot14^{k-1}\)：加回 \((1,A)\) 的交集
- \(-13^k\)：减去三者的交集
solve
- 对 \(k\) 从 1 到 16 调用
count_k并累加，返回总和。
输出
f"{result:X}"将整数格式化为大写十六进制字符串，无前缀，符合题目要求。