题解 08

暑假快结束了。

2021 杭电多校 07 1004 Link with Balls

$2n$ 个盒子，编号从 1 开始，从第 $2x - 1$ 个盒子可以拿 $kx$ 个球；从第 $2x$ 个盒子可以拿至多 $x$ 个球。$k$ 是非负整数。求一共拿到 $m$ 个球的方法数，答案对 $10^9 + 7$ 取模。
$1 \le T\le 10^5, 1\le n, m\le 10^6$

组合数学题。

看到 $2n$ 一般想到两两配对，然后发现拿 $kx$ 个球的盒子和至多拿 $x - 1$ 个球的盒子可以组合出任意数量的球，而且数量和取法一一对应，那么就是 $n$ 个能拿任意个球的盒子和 $1$ 个能拿 $[0, n]$ 的盒子中取出一共 $m$ 个。

枚举从 $[0, n]$ 盒子中拿出的数量，对于剩下的用插板法分开，添加 $n - 1$ 个位置表示板子之间为空，得到 $\sum{i = 0}^{n}C{m - i + n - 1}^{n - 1}$，这个式子直接算会超时，用组合数公式化简成 $C{m + n}^{m} - C{m - 1}^{n}$。预处理组合数即可。

2021 杭电多校 07 1005 Link with EQ

一排一共 $n$ 个座位，每个人会选择自己的座位，使自己到已经坐下的所有人最小距离尽量大。有多个可选座位时随机选一个，第一个人会随机选座。当最小距离最大是 $1$ 时，认为这排座位已满。给定座位数量，求座位“已满”时座位上总人数的期望值，对 $10^9 + 7$ 取模。
$1\le T\le 10^5, 1\le n\le 10^6$

概率 dp，主要想清楚子情况的分类。

令两端有人时，$n$ 个空座位的期望人数是 $f(n)$，一端有人时的期望是 $g(n)$，那么它们的递推公式：

$$\begin{split} &f(n) = \begin{cases} &0 &n = 1, 2\\[2ex] &f(\lfloor \frac{n}{2}\rfloor) + 1 + f(n - 1 - \lfloor \frac{n}{2}\rfloor) &others \end{cases}\\[2ex] &g(n) = \begin{cases} &0 &n = 1\\[2ex] &f(n - 1) + 1 &others \end{cases} \end{split}$$

以上两个式子，代入情景就能推出来。接下来计算答案。

对于第一个来的人，有 $n$ 个等可能的选择，遍历求和即可，但是同样会超时。记答案为 $h(n)$ 优化一下式子：

$$\begin{split} h(n) = & \frac{1}{n}\sum_{i = 0}^{n - 1}g(i) + 1 + g(n - 1 - i)\\[2ex] = & 1 + \frac{1}{n}\sum_{i = 0}^{n - 1}g(i) + \frac{1}{n}\sum_{i = 0}^{n - 1}g(n - 1 - i)\\[2ex] = & 1 + \frac{2}{n}\sum_{i = 0}^{n - 1}g(i) \end{split}$$

维护一下前缀和就好了。

2021 杭电多校 07 1006 Link with Grenade

随机向一个方向以速度 $v$ 投掷一颗起爆时间 $t$，杀伤半径 $r$ 的手雷。手雷从被投出的那一刻开始倒计时，求投掷点不被炸到的概率，对 $10^9 + 7$ 取模。
三维空间，假设手雷不会触地，加速度 $10m/s^2$。
$1\le T\le 10^5, 1\le t, v, r\le 100, t, v, r 是整数$

计算几何题。一开始用随机取弧度去算，一直化不出有理数。后来一查，发现因为面积元的问题，随机弧度获得的点在单位球表面并不是均匀的，我原来的式子还要积出面积。至于证明，是高数下的内容我当然忘光了。

不会炸到的投掷方向，形成的是一个向下的球冠，算出它与整个球面的面积比即可。

题解的模型是，把重力加速度反向给投掷点，分开计算投掷点到手雷的距离，得到一个三角形，三边长都已知。可以求出投掷点和手雷位移夹角的三角函数，这个夹角增大时扫过的那块球冠就是安全的部分，诱导公式换一下方向就能算出来。

如果用我一开始的模型，设速度的水平仰角是 $\theta$，分解速度之后算出让投掷点恰好在爆炸边界的仰角（的正弦），这个仰角把球面分成了两个球冠，求仰角减小时扫过的球冠面积。注意这里的加速度和上一个模型反向，化简比较两个结果的时候有点头疼。

两个模型其实只是变换一下坐标系的区别。

2021 杭电多校 07 1009 Smzzl with Safe Zone

平面内，一大一小两个凸包，小凸包是大凸包的子集。小凸包有 $m$ 个顶点，大凸包有 $n$ 个顶点。
定义一点到一个凸包的距离为该点到凸包所有边线段距离的最小值，求大凸包上任一点到小凸包的最远距离，输出距离的平方，对 $10^9 + 7$ 取模。
$1\le T \le 10^4, 3\le m, n\le 10^5, |x|, |y| \le 10^7, \sum m, \sum n\le 10^6, 顶点按逆时针顺序给出$

显然是计算几何。

首先，不需要考虑大凸包上的各个点，只要考虑顶点即可：如果点在的边和最近的边不平行，显然是端点距离最小；如果平行，可以移动到边的端点。

然后是旋转卡壳的一个性质（？）。假设我们有这个顶点以及它最近的边，逆时针枚举下一个顶点，最近的边一定也在逆时针方向，注意不一定是相邻的边。而凸包外一个顶点到各边的距离，按时针顺序排下来长得像二次函数，那么可以用双指针的方法去找最近的边，而不是对于每个顶点都枚举所有边。

最后一定要注意的一点：这题的数据范围允许 double，但是不允许 long long 的平方直接计算距离，比较长度的时候需要用 double，更新答案的时候用对应的 long long 取模。存在丢失精度的问题，但是这题好像不影响。计算几何的题目代码很长，别敲错了。

2021 杭电多校 07 1012 Yiwen with Sqc

给定一个小写字母串 $s$，求所有字符在所有子串中出现次数的平方和，答案对 $998244353$ 取模。
$1\le T\le 100, |s|\le 10^5, \sum |s|\le 5\times 10^6$

字符串 + 加法卷积（忘记了的词）。就目前接触到的字符串题目，做法其实比其他类型杂乱。

显然把各种字符分开记录。当场看出了每个字符的贡献应该用差分相关的东西去做，然后推了半天推不出来。赛后看题解用了二次差分，感觉不太能想到。

推式子的话可以这样做，对于一种字符，记 $s[1, n]$ 是它在各个前缀里出现的次数，有：

$$\begin{split} ans = & \sum_{i = 1}^{n}\sum_{j = i}^{n}(s_j - s_{i - 1})^2\\[2ex] = & \sum_{i = 1}^{n}\sum_{j = i}^{n}s_j^2 + s_{i - 1}^2 - 2\times s_j s_{i - 1}\\[2ex] = & n\sum_{i = 1}^{n}s_i^2 - (\sum_{i = 1}^{n}{s_i})^2 + \sum_{i = 1}^{n}s_i^2\qquad 多项和平方\\[2ex] = & (n + 1)\sum_{i = 1}^{n}s_i^2 - (\sum_{i = 1}^{n}{s_i})^2 \end{split}$$

这样维护一下前缀就可以超时了。对于每个字符提取出来的离散位置，计算出每段的长度，也可以完成。考虑在头加一个 0 统一下标，末尾加一个 n + 1 简化循环。

注意溢出。