自动搬运

查看原文

来自洛谷，原作者为

	Unnamed114514 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 22:49:54，当前版本为作者最后更新于2023-08-20 13:20:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Update

2023.8.28 转移矩阵好像有个地方写错了。

---

操作

被出题人强制要求，于是把题解写详细点。

Subtask 0

状压，每个人共三个状态：不在团队中（$0$），是团队成员（$1$），不是团队成员（$2$）。

那么我们就能定义 $dp_{i,j}$ 表示当前是第 $i$ 次操作，并且状态为 $j$ 的期望管理员数，用三进制按照题目模拟即可。

时间复杂度 $O(n3^a)$，期望得分 $25$。

Subtask 1&2

容易想到管理员总数的期望等于每个人成为管理员的期望和，又因为每个人的贡献为 $1$，所以就是等价于求概率。

对于 $dp_{i,0/1/2}$ 表示一个人经过 $i$ 次操作后不在团队中/是团队成员/是团队管理员的概率。

对于 $dp_{i,0}$，那么可以由上一次的成员踢出，也可能是上一次不在团队内，这一次进行了无效操作，转移为 $dp_{i,0}\gets\dfrac{3}{4}dp_{i-1,0}+\dfrac{1}{4}dp_{i-1,1}$。

对于 $dp_{i,1}$，那么可以由上一次的管理员变成成员，上一次不在团队内这一次加入，也可能是上一次设置为团员后，这一次进行了无效操作，转移为 $dp_{i,1}\gets\dfrac{1}{4}dp_{i-1,0}+\dfrac{1}{2}dp_{i-1,1}+\dfrac{1}{4}dp_{i-1,2}$。

对于 $dp_{i,2}$，那么可以由上一次的成员设置为管理员，也可能是上一次的管理员这一次进行了无效操作，转移为 $dp_{i,2}\gets\dfrac{1}{4}dp_{i-1,1}+\dfrac{3}{4}dp_{i-1,2}$。

那么我们在初始化了 dp 后，原问题就转化为了求每个 $a$ 的出现次数。

时间复杂度 $O(n\log n)$，瓶颈是在统计出现次数，期望得分 $70$。

Subtask 3

首先根据余数的周期性，可以发现：对于同一个 $x$，它们下一次操作得到的 $x'$ 是相同的。

那么 $a$ 就有周期性，并且最多只有 $q$ 个 $a$，那么我们可以暴力统计每个 $a$ 的出现次数。

但是 dp 不能初始化，但是发现这个递推式非常特殊，于是考虑矩阵加速：

目标矩阵应该很好拿到：

$$\begin{bmatrix} f_{i,0}\\ f_{i,1}\\ f_{i,2} \end{bmatrix} $$

设矩阵加速的转移如下：

$$\begin{bmatrix} f_{i-1,0}\\ f_{i-1,1}\\ f_{i-1,2} \end{bmatrix}\times\begin{bmatrix} a\ b\ c\\ d\ e\ f\\ g\ h\ i \end{bmatrix}=\begin{bmatrix} f_{i,0}\\ f_{i,1}\\ f_{i,2} \end{bmatrix} $$

根据矩阵乘法，我们可以得到如下的方程：

$$f_{i,0}=af_{i-1,0}+bf_{i-1,1}+cf_{i-1,2}$$ $$f_{i,1}=df_{i-1,0}+ef_{i-1,1}+ff_{i-1,2}$$ $$f_{i,0}=gf_{i-1,0}+hf_{i-1,1}+if_{i-1,2}$$

带入上面的状态转移方程，有：

$$\begin{cases}a=\frac{3}{4}\\b=\frac{1}{4}\\c=0\\d=\frac{1}{4}\\e=\frac{1}{2}\\f=\frac{1}{4}\\g=0\\h=\frac{1}{4}\\i=\frac{3}{4}\end{cases} $$

那么矩阵加速的矩阵乘法就应该是这样的：

$$\begin{bmatrix} f_{i-1,0}\\ f_{i-1,1}\\ f_{i-1,2} \end{bmatrix}\times\begin{bmatrix} \frac{3}{4}\ \frac{1}{4}\ 0\\ \frac{1}{4}\ \frac{1}{2}\ \frac{1}{4}\\ 0\ \frac{1}{4}\ \frac{3}{4} \end{bmatrix}=\begin{bmatrix} f_{i,0}\\ f_{i,1}\\ f_{i,2} \end{bmatrix} $$

那么转移矩阵就是：

$$\begin{bmatrix} \frac{3}{4}\ \frac{1}{4}\ 0\\ \frac{1}{4}\ \frac{1}{2}\ \frac{1}{4}\\ 0\ \frac{1}{4}\ \frac{3}{4} \end{bmatrix}$$

初始化 $f_{0,0}\gets 1$，那么初始矩阵就是：

$$\begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}$$

对于每次乘上转移矩阵，就会从 $i-1$ 转移到 $i$，那么令一个数的出现次数为 $cnt$，我们只需要用初始矩阵乘上转移的 $cnt$ 次方即可，最后我们需要的是成为管理管的概率，所以最后当前的概率就是目标矩阵的第 $3$ 行第 $1$ 列。

时间复杂度 $O(q\log n)$，期望得分 $100$。