YCup Stage 7. 单身（出题人题解）

A（Hard）

前置知识：同余

题目要求 $a_k a_j \leq \frac{3}{4}$ 对应任意 $k, j$。取 $k=j$ 可得 $a_k^2 \leq \frac{3}{4}$，即 $|a_n| \leq \frac{\sqrt{3}}{2}$。这意味着对于所有 $n$，角度 $\pi(b_1 q^{n-1} p + \phi)$ 必须落在非红色区域内。

设 $x_n = b_1 q^{n-1} \pmod{26}$。这意味着在模 $26$ 的圆周上，序列 ${x_n}$ 产生的点集在圆周上的最大相邻间隙必须大于 $\frac{26}{3}$。

若 $q=3$，序列为 $b_1 3^{n-1} \pmod{26}$，其轨道周期满足 $3^3 = 27 \equiv 1 \pmod{26}$，故轨道最多只有 $3$ 个点，根据鸽巢原理，圆周上任意 $3$ 个点必存在一个间隙 $\geq \frac{26}{3}$，因此总能通过调整 $\phi$ 将这最多 3 个点进行平移，使之满足条件。

当 $q=2$ 时，轨道 $2^n \pmod{26}$ 无法保证对任意 $b_1$ 都有足够大的间隙。

因此最小的 $q=3$。

B（Extreme）

前置知识：$k$ 进制（$k$ 为大于 $1$ 的任意整数）

考虑系数非负，也就是说 $x$ 不小于 $1$ 时，多项式值一定不小于所有系数之和，也就不小于任意一个系数。

记下 $x=1$ 的多项式值 $m$ 并且第二次询问 $m+2$ 即可。记下这个结果并且转换为 $m+2$ 进制，此时可以发现，每一项都是多项式的一个系数。用短除法得出每一位即可。

为什么这样确定的多项式唯一？

因为第一次询问得到的 $m = P(1)$ 是多项式所有系数之和，且由于系数非负，故每一个系数 $c_i$ 均不大于 $m$。当第二次询问输入 $M = m+2$ 时，多项式值 $P(M) = c_0 + c_1 M + c_2 M^2 + \dots + c_n M^n$。由于所有的系数 $c_i \le m < M$，在 $M$ 进制表示下，每个系数 $c_i$ 恰好对应 $P(M)$ 在该进制下的各个数位上的数字。根据 $M$ 进制表示的唯一性，多项式的各项系数 $c_i$ 被唯一且无歧义地确定。

为什么一次不行？考虑存在一次多项式 $bx+m$，而只通过一次询问，你会得到一个不定方程，这种方程的解是不唯一的。因此通过 $1$ 次没有办法确定任何一个给出的多项式。

因此答案为 $2$。

C（Easy）

注意到原式可化为 $2 \cos(\alpha - \beta)$。

当 $\alpha=\beta=\frac{\sqrt{2}}{4}$ 时，原式有最大值 $2$。

D（Medium）

诈骗题，题目里面那些数字全都是在整活。

考虑以下一个情况————当里面有 $A$ 个红球，$B$ 个蓝球的时候，取出红球的概率是 $\frac{A}{A+B}$

不妨假设里面有 $A$ 个红球，$B$ 个蓝球的时候，抽中蓝球，则会向罐中补充 $P$ 颗蓝球；否则，会向罐中补充 $P$ 颗红球，第 $k$ 轮取出红球的概率是 $\frac{A}{A+B}$：

第一轮取出红球：可将后续 $k$ 轮视作一次 $k$ 轮的完整过程，则第 $k+1$ 轮取出红球的概率是 $\frac{A+P}{A+B+P}$。
第一轮取出蓝球：可将后续 $k$ 轮视作一次 $k$ 轮的完整过程，则第 $k+1$ 轮取出红球的概率是 $\frac{A}{A+B+P}$。

根据全概率公式即可得到第 $k+1$ 轮的概率是 $\frac{A}{A+B} \cdot \frac{A+P}{A+B+P}+\frac{B}{A+B} \cdot \frac{A}{A+B+P}=\frac{A}{A+B}$。

因此我们得到了一个十分牛逼的结论：概率不变。

所以答案其实就是 $\frac{799}{799+325}=\frac{799}{1124}$

E（Medium）

不妨把第一个点的位置标作 $1$，并顺时针标注所有点。总计有 $2025 \cdot 2024$ 种选择方式。

第二次选中 $1014$ 的时候由于是直径，所以没有点可以成立。

当选中 $N \in [2,1013]$ 的时候，可以选择的范围是 $(1013,N+1013)$，总计有 $N-1$ 个。由对称性，当 $N \in [1015,2026]$ 的时候方案数相同。

因此符合条件的选择数为 $2\sum_{k=1}^{1012}=1012 \cdot 1011$。

因此可得总选择数为 $\frac{1012 \cdot 1011}{2025 \cdot 2024}=\frac{337}{1350}$

F（Easy-Medium）

考虑一定存在一个合法方案，因此考虑最后的形态。

计算所有三角形的内角和总和：对于不在凸多边形上的点，以其为顶点的内角之和为 $2\pi$；对于在凸多边形上的点（设为 $k$ 个），这些点上的三角形内角的和就是凸多边形的内角和即 $(k-2)\pi$，因此总内角和是 $2(2026-k)\pi+(k-2)\pi=(4050-k)\pi$，总三角形数为 $4050-k$。

考虑边数最小的合法凸多边形为三角形，因此 $k$ 取 $3$ 有最大值 $4047$。

G（Medium）

截面的最高点 $A$、最低点 $B$ 与圆锥轴线必定共面。由于圆锥高 $H$ 等于底面半径 $R$，轴截面是一个等腰直角三角形。设底面圆心为 $O(0,0)$。由于 $OA \perp OB$，在轴截面（二维平面）内，设 $A$ 点坐标为 $(r_a, z_a)$，$B$ 点坐标为 $(-r_b, z_b)$。

根据 $H=R$，可知 $r_a = H - z_a$，$r_b = H - z_b$。

$\vec{OA} \cdot \vec{OB} = -r_a r_b + z_a z_b = 0$

即 $-(H - z_a)(H - z_b) + z_a z_b = 0$

即 $-H^2 + H(z_a + z_b) = 0 \implies z_a + z_b = H$

椭圆中心点 $M$ 是 $AB$ 的中点，其高度 $z_M = \frac{z_a + z_b}{2} = \frac{H}{2}$。已知 $H=2026$，故高度恒为 $1013$。

由于题目要求取值集合，故取值集合为 ${1013}$，答案为 $1013$。

H（Medium-Hard）

由 $|\vec{c} - 3\vec{a}| = 2|\vec{c}|$ 两边平方化简：

$\vec{c}^2 - 6\vec{c}\cdot\vec{a} + 9\vec{a}^2 = 4\vec{c}^2$
代入 $|\vec{a}|=3$，得 $3\vec{c}^2 + 6\vec{c}\cdot\vec{a} - 81 = 0 \implies \vec{c}^2 + 2\vec{c}\cdot\vec{a} - 27 = 0$。

$\vec{c} = \lambda\vec{a} + \mu\vec{b}$ 且 $\lambda + \mu = 2$。
将 $\mu = 2 - \lambda$ 代入上述轨迹方程，利用 $|\vec{a}|=3, |\vec{b}|=2, \vec{a} \cdot \vec{b} = 3$ 展开： $7\lambda^2 + 8\lambda + 1 = 0$

该方程根为 $\lambda_1 = -1, \lambda_2 = -1/7$。

所求表达式 $\sum (\lambda_i + \mu_i + \lambda_i \mu_i) = \sum (2 + \lambda_i(2 - \lambda_i))$。

代入计算得总和为 $\frac{34}{49}$。

I（Easy）

首先 $OA,OB,OC$ 一定都是 $6$，因为不是意味着你可以任意移动这三个点，自然可以往远离对边的方向移动，使得面积变大。

其次 $A,B,C$ 一定在这个球心为 $O$，半径为 $6$ 的球体的大圆上，对于任何不在大圆上的三角形都可以构造一个在大圆上的相似三角形，使得其面积更大。

再其次，对于任何一个非等边三角形，你都可以选择一个边，让剩下两个边长度不相等，此时固定选择的边的两个顶点，移动另一个顶点，因为固定这条边以后，最大值在剩下两个边长度相等时取到，这个可以画图证。

然后只有等边三角形不能这么干，其他任何三角形都存在比他大的三角形，因此最大值就是等边三角形。

J（Hard~Extreme）

先确定上界。

我们将相邻项之差绝对值之和写为： $$S = \sum_{i=1}^{n-1} |a_{i+1} - a_i| = \sum_{i=1}^{n} c_i a_i$$ 其中 $c_i$ 为每个元素 $a_i$ 在求和展开式中的净系数。由于每一个绝对值项 $|a_{i+1} - a_i|$ 展开后均为 $\pm(a_{i+1} - a_i)$，因此边界项 $a_1$ 和 $a_n$ 在展开式中的系数只能为 $\pm 1$，而其余中间项 $a_i (1 < i < n)$ 的系数只能为 $-2, 0, 2$。此外，所有系数之和显然为 $0$。

为了使 $S$ 最大，我们应当让较大的元素分配到正系数，较小的元素分配到负系数。

设 $n = 2m = 2026$（其中 $m = 1013$）。最大可能情况是将 $+2$ 分配给最大的 $m-1$ 个数 ${m+2, \dots, 2m}$，将 $+1$ 分配给 ${m+1}$，将 $-1$ 分配给 ${m}$，并将 $-2$ 分配给最小的 $m-1$ 个数 ${1, \dots, m-1}$。

由此可得 $S$ 的上界 $M$ 为： $$M = 2 \sum_{i=m+2}^{2m} i + (m+1) - m - 2 \sum_{i=1}^{m-1} i = 2(m^2 - 1) + 1 = 2m^2 - 1$$

代入 $m = 1013$，得： $$M = 2 \times 1013^2 - 1 = 2052337$$

然后我们可以证明这个上界是可以达到的：我们可以构造出如下的一种方案，来达到上界：

将集合 ${1, \dots, 2m}$ 划分为较小元素集 $L = {1, \dots, m}$ 和较大元素集 $R = {m+1, \dots, 2m}$。

只要排列 $a_1, \dots, a_{2m}$ 满足大小元素交错（即奇数位均来自 $L$，偶数位均来自 $R$），由于 $R$ 中的任意元素均严格大于 $L$ 中的任意元素，此时所有相邻项之差的绝对值都可以直接去掉。

例如，对于 $L R L R \dots L R$ 型排列，展开后有： $$S = (a_2 - a_1) + (a_2 - a_3) + (a_4 - a_3) + \dots + (a_{2m} - a_{2m-1}) = 2 \sum_{i=1}^{m-1} a_{2i} + a_{2m} - a_1 - 2 \sum_{i=2}^{m} a_{2i-1}$$

此时，只要令 $a_{2m} = m+1$（$R$ 中最小元素），$a_1 = m$（$L$ 中最大元素），并将 ${m+2, \dots, 2m}$ 任意排在其余偶数位，将 ${1, \dots, m-1}$ 任意排在其余奇数位，即可完全达到上界 $M = 2m^2 - 1$。

达到最大值的排列必然呈现交错形态，且只有两种基本布局：$L R L R \dots L R$ 和 $R L R L \dots R L$。

在 $L R L R \dots L R$ 布局中：

• 最小元素 $m+1 \in R$ 的位置被固定在 $a_{2m}$，其余 $m-1$ 个大元素有 $(m-1)!$ 种排列方式；
• 最大元素 $m \in L$ 的位置被固定在 $a_1$，其余 $m-1$ 个小元素有 $(m-1)!$ 种排列方式；

因此该布局下的合法排列数为 $[(m-1)!]^2$。

由对称性，$R L R L \dots R L$ 布局下的合法排列数亦为 $[(m-1)!]^2$。

故达到最大值的总排列数 $k$ 为： $$k = 2 \cdot [(m-1)!]^2$$

因此可得：

代入 $m = 1013$，得 $k = 2 \cdot [1012!]^2$。我们需要求 $M + \ln k$ 的整数部分。

这个答案可以通过卡西欧求和功能计算——本题目的精度设置特意设置了一个较低的精度要求。当然，也存在不需要卡西欧求和功能的方法。

由斯特林公式（Stirling's approximation）高精度近似： $$\ln(N!) \approx N \ln N - N + \frac{1}{2} \ln(2\pi N)$$

代入 $N = 1012$，并精确计算自然对数：

• $\ln(1012) \approx 6.9196839$
• $N \ln N - N \approx 1012 \times 6.9196839 - 1012 = 5990.7201$
• $\frac{1}{2} \ln(2\pi N) = \frac{1}{2} \ln(2024\pi) \approx \frac{1}{2} \times 8.7576 = 4.3788$

由此可得 $\ln(1012!) \approx 5990.7201 + 4.3788 = 5995.0989$。

进而计算 $\ln k$： $$\ln k = \ln 2 + 2 \ln(1012!) \approx 0.6931 + 2 \times 5995.0989 = 11990.8909$$

故 $\lfloor M + \ln k \rfloor = 2052337 + \lfloor 11990.8909 \rfloor = 2052337 + 11990 = 2064327$。