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
| 好的，我们先明确一下问题。
---
## 1. 问题回顾
- \( T(N, m) \) 是确保从 \( N \) 根保险丝（其中 \( m \) 根是好的）中 **必定** 测出两根好的（分别放在 A 和 B 位置）所需的最少测试次数（最坏情况下）。
- 前面推理得到：
\[
T(N, m) = \binom{N}{2} - e(T(N, m-1)) + 1
\]
吗？不对，我们重新整理一下。
实际上，我们是用图论模型：
- 顶点是 \( N \) 根保险丝。
- 一次测试是选两个不同的顶点连边（测试这对保险丝）。
- 好保险丝集合 \( G \) 大小为 \( m \)。
- 成功当且仅当测试的某条边两端都在 \( G \) 中。
- 我们要保证任何 \( m \) 个顶点的子集中至少有一条测试过的边。
- 这等价于：测试的边集 \( E \) 的补图中没有 \( m \) 个顶点的团（即 \( K_m \)）。
- 所以问题变成：求最小的 \( k \) 使得存在一个 \( k \) 条边的图，它的补图是 \( K_m \)-free。
由 Turán 定理：
\[
\text{最大 } K_{m}\text{-free 图的边数} = e(T(N, m-1))
\]
所以：
\[
\text{补图的最大边数} = e(T(N, m-1))
\]
因此：
\[
|E| = \binom{N}{2} - e(T(N, m-1))
\]
是 **可能不包含任何 \( G \) 中的边** 的最大边数（即最坏情况设计）。
我们要的是 **必须包含至少一条 \( G \) 中的边** 的最小 \( |E| \)，所以：
\[
T(N, m) = \binom{N}{2} - e(T(N, m-1)) + 1
\]
因为如果测试了 \( \binom{N}{2} - e(T(N, m-1)) \) 条边，仍可能有一个 \( m \) 个顶点的集合（即 Turán 图 \( T(N, m-1) \) 的一个部集的某个选取）中无边；再多 1 条边就必然命中。
---
## 2. 公式化简
已知：
\[
e(T(N, r)) = \frac12\left( N^2 - s(q+1)^2 - (r-s)q^2 \right)
\]
其中 \( q = \lfloor N/r \rfloor, s = N \bmod r \)。
于是：
\[
T(N, m) = \binom{N}{2} - e(T(N, m-1)) + 1
\]
\[
= \frac{N(N-1)}{2} - \frac12\left( N^2 - s(q+1)^2 - ((m-1)-s)q^2 \right) + 1
\]
其中 \( q = \lfloor N/(m-1) \rfloor, s = N \bmod (m-1) \)。
---
其实更简单：
\[
T(N, m) = \binom{N}{2} - e(T(N, m-1)) + 1
\]
\[
e(T(N, m-1)) = \left\lfloor \frac{N^2}{2} \left( 1 - \frac{1}{m-1} \right) \right\rfloor
\]
吗？不完全是，当 \( N \) 不能被 \( m-1 \) 整除时，要减去 \( \frac{s(m-1-s)}{2(m-1)} \)。
但我们可以直接用整数公式：
\[
e(T(N, r)) = \frac12 \left( N^2 - (N \bmod r)\left\lceil \frac{N}{r} \right\rceil^2 - (r - (N \bmod r)) \left\lfloor \frac{N}{r} \right\rfloor^2 \right)
\]
其中 \( r = m-1 \)。
---
## 3. 计算 \( L(N) \)
\[
L(N) = \sum_{m=2}^N T(N, m)
\]
\[
= \sum_{m=2}^N \left[ \binom{N}{2} - e(T(N, m-1)) + 1 \right]
\]
\[
= \sum_{m=2}^N \binom{N}{2} + \sum_{m=2}^N 1 - \sum_{m=2}^N e(T(N, m-1))
\]
\[
= (N-1)\binom{N}{2} + (N-1) - \sum_{r=1}^{N-1} e(T(N, r))
\]
因为当 \( m=2 \) 时 \( r=1 \)，\( m=N \) 时 \( r=N-1 \)。
---
## 4. 程序实现
我们只需高效计算：
\[
S(N) = \sum_{r=1}^{N-1} e(T(N, r))
\]
然后：
\[
L(N) = (N-1)\binom{N}{2} + (N-1) - S(N)
\]
\[
= (N-1)\frac{N(N-1)}{2} + (N-1) - S(N)
\]
\[
= \frac{N(N-1)^2}{2} + (N-1) - S(N)
\]
---
**计算 \( e(T(N, r)) \)**：
\[
q = N / r, \; s = N \% r
\]
\[
e = (N*N - s*(q+1)*(q+1) - (r-s)*q*q) / 2
\]
注意这里用整数除法。
---
## 5. 复杂度
直接对 \( r=1 \) 到 \( N-1 \) 求和是 \( O(N) \)，对于 \( N=10^7 \) 可行（几秒）。
---
## 6. C++ 代码
|
