P9590 PFL 团主的 PFL 操作 题解

· · 题解

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}

那么转移矩阵就是：

\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。