2023.9.3 闲话

T1

一个随机数生成器会随机生成 $[0,n)$ 之间的整数。给定 $m$ 个互不相同的整数 $a_i$，如果某一次生成的数在这 $m$ 个数当中就停止，否则继续下一次生成。求生成的所有数之和的期望。

$1\leq m\leq n\leq 10^7$，$0\leq a_i<n$。

发动技能「自信」，认为答案和 $a_i$ 无关。

考虑设 $f(i)$ 表示在第 $i$ 次生成后停止的第 $i$ 个数的期望贡献。则有

$f(i)=\left(\dfrac{n-m}{n}\right)^{i-1}\times\dfrac{n-1}{2}$

那么答案就是

$\sum_{i=1}^{\infty}f(i)=\dfrac{n-1}{2}\sum_{i=1}^{\infty}\left(\dfrac{n-m}{n}\right)^{i-1}$

等比数列求和得到

$\dfrac{n(n-1)}{2m}$

时间复杂度 $\mathcal{O}(1)$。

T4

一个比较 tricky 的题目。

这些操作都比较难用普通的线段树操作来维护，介绍一个线段树维护矩阵的技巧。

我们把一个点看成行向量 $(x,y,1)$，对所有操作分别构造转移矩阵。

• 平移，相当于 $(x,y)\rightarrow (x+p,y+q)$。

$\begin{pmatrix} x&y&1\end{pmatrix}\begin{pmatrix}1&0&0 \\ 0&1&0\\ p&q&1\end{pmatrix}=\begin{pmatrix}x+p&y+q&1\end{pmatrix}$

• 沿 $x$ 轴翻转，相当于 $(x,y)\rightarrow (x,-y)$。

$\begin{pmatrix} x&y&1\end{pmatrix}\begin{pmatrix}1&0&0 \\ 0&-1&0\\ 0&0&1\end{pmatrix}=\begin{pmatrix}x&-y&1\end{pmatrix}$

• 沿 $y$ 轴翻转，相当于 $(x,y)\rightarrow (,-xy)$。

$\begin{pmatrix} x&y&1\end{pmatrix}\begin{pmatrix}-1&0&0 \\ 0&1&0\\ 0&0&1\end{pmatrix}=\begin{pmatrix}-x&y&1\end{pmatrix}$

• 沿 $y=x$ 翻转，相当于 $(x,y)\rightarrow (y,x)$。

$\begin{pmatrix} x&y&1\end{pmatrix}\begin{pmatrix}0&1&0 \\ 1&0&0\\ 0&0&1\end{pmatrix}=\begin{pmatrix}y&x&1\end{pmatrix}$

• 逆时针旋转 $\alpha$，相当于 $(x,y)\rightarrow (x\cos\alpha-y\sin\alpha,x\sin\alpha+y\cos\alpha)$。

$\begin{pmatrix} x&y&1\end{pmatrix}\begin{pmatrix}\cos\alpha&\sin\alpha&0 \\ -\sin\alpha&\cos\alpha&0\\ 0&0&1\end{pmatrix}=\begin{pmatrix}x\cos\alpha-y\sin\alpha&x\sin\alpha+y\cos\alpha&1\end{pmatrix}$

线段树维护转移矩阵乘法即可。

时间复杂度 $\mathcal{O}(n\log n)$。矩阵乘法自带大常数，但是可以接受。