24pht春5

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/138623622

pht春5

A

相当于规定了每一位的操作次数的奇偶性。

随便排序显然不影响。

因此有 $f_i=f_{i-1}\times \dfrac i n+f_{i+1}\times \dfrac{n-i}n$ ，是个经典问题，差分一下？

---

设 $f_i$ 表示当前 $i$ 个正面到 $n$ 个操作次数的期望。

递推边界 $f_n=0$

$$f_i=\dfrac i n f_{i-1}+\dfrac{n-i}nf_{i+1}$$

又有向上，又有向下。

但是 $f_0=1+f_1$ 。此类问题解法：待定系数法。

设 $f_i=a_if_0+b_i$ 。

则

$$a_if_0+b_i=\dfrac i n (a_{i-1}f_0+b_{i-1})+\dfrac{n-i}n(a_{i+1}f_0+b_{i+1})$$

然后可以推出 $a,b$ 分别的转移式。

$a_1,b_1$ 是什么事易求的。

由 $f_n=a_nf_0+b_n$ 可以反求 $f_0$ 。

然后由 $f_i=a_if_0+b_i$ 可以反求 $f_i$ 。

---

更简单的做法：

设 $d_i$ 表示首次从有 $i$ 个相同到 $i+1$ 个相同的期望次数（也就是差分法）

$$d_i=1+\frac i n \times 0+\frac{n-i}n(d_{i-1}+d_i)$$

那么 $f_i=\sum_{j\ge i}d_j$

就可以从小往大推 $d_i$ ，再从大往小推 $f_i$ ，就做完了。

B

一道题测出我极低的概率期望水平。

盲测了个结论，然后自己也不知道为什么，因为过了样例交就过了。

大概就是先算出当前末尾期望长度 $f$ 。然后正常应该是要加 $2f-1$ 的期望，但是事实证明加 $2f-p$ 才能过，非常神奇，我也不知道为什么，可能是因为本身就要乘个 $p$ ，然后我在 $f$ 那里已经乘了，那么这里就需要给1单独乘。

你看，如果不计这一位，就相当于加 $p\times(2f+1)$ ，那就解释得通了。

---

考虑第 $i$ 个位置对答案的贡献 $d_i$ （增量贡献）。

求出第 $i$ 个的期望长度是 $f_i$ 。

对于 $f_i$ ：

$f_i=(1-p_i)\times 0 + p_i\times (f_{i-1}+1)$

则 $d_i=[f_i]^2-[f_{i-1}]^2$

但是算期望不能直接丢进去算平方会出问题。

考虑 $[f_i]^2=(1-p_i)\times 0+ p_i\times (f_{i-1}+1)=p_i\times [f_{i-1}]^2+2p_if_{i-1}+p_i$

期望乘数是没问题的，但是期望乘期望有问题。

定义 $g_i$ 表示长度的期望的平方。

则 $g_i=p_i g_{i_1}^2+2p_if_{i-1}+p_i$

后面那个就是 $2p_if_{i-1}+p_i$ 增量部分。

答案为 $\sum(2p_if_{i-1}+p_i)$

这个和之前推出来的一样

C

为什么我按照上题打就不行呢？不就是2次变成3次吗？

---

不知道为什么错？

直接上转移：

$$f_i=(1-p)\times f_{i-1}+\sum_j(f_{j-1}+(i-j)^3)\dfrac{s_i}{s_j}(1-p_j)$$

然后拆开成每一项分别计算贡献。

还有去讨论恶心的 $p=0$ 的情况。

然后WA了，我也不知道为什么。

下次还是先看完所有题思考完再去打吧。之前那个策略对我来说还是有用的。

---

一样的。平方变成三次方。

$$f_i=p_i\times (f_{i-1}+1)$$

$$g_i=p_i\times (g_{i-1}+2f_i+1)$$

由 $(x+1)^3=x^3+2x^2+2x+1$ 得 ：

$$h_i=p_i\times (h_{i-1}+3g_{i-1}+3f_{i-1}+1)$$

发现后面那坨才是增量。

所以答案就是 $\sum p_i(3g_{i-1}+3f_{i-1}+1)$

本质是因为期望不能数乘，只能期望和概率在一起。

D

好像直接上图了，然后还是那个经典平方问题。

但我现在C也没搞出来，就不想思考了

---

由线性图变成任意图了。

设 $f_{i,j,k}$ 表示现在在 $i$ 号点，有 $j$ 的等级，走了 $k$ 步的期望代价。

在这类模型里， $j$ 是可以不要的。

新状态： $f_{i,k}$ 现在在 $i$ 号点，走了 $k$ 步的期望（Level期望 + Level^2的期望+概率）。

• $P_k(u)$ 落在 $u$ 的概率

• $L_k(u)$ Level期望

• $E_k(u)$ Level^2的期望

对于 $u\to v$ ，都可以去转移，概率是 $\dfrac 1 {c_u}$ ，这个记为 $c_u$ 的概率。

$P_k(u)\times \dfrac 1 {c_u}\to P_{k+1}(v)$

下一步取决于 $C_v$

1. $p(L_k(u)+P_k(u))\to L_{k+1}(v)$

2. $p(L_k(u)+2L_k(u)P_k(u)+P_k^2(u))\to E_{k+1}(v)$

对于另一种情况：

$pL_k(u)\to L_{k+1}(v)$

然后还要 $ans+=c_uE_k(u)$

此题和上题区别在于每个节点不是必然到达，所以需要记录多一维表示概率。

---

不知道为什么这么一道小丑题我调这么久。

E

原题，忘记当时做法了。到时候pht讲的时候直接记一次笔记来理解算了

---

假如从期望dp应该从手里有多少个饼干来刻画。

我们先把 $a$ 弄出来，然后 $\sum a = M$ 。任何一个多重集合在变化过程中都可能出现。

$$f(A)=1+\sum\dfrac {a_i} m \sum \dfrac 1 {n-1} f(A')$$

显然没法直接用动态规划来解决。

考虑技巧，把 $A=\{a_1,a_2,\dots,a_n\}$

希望存在这么一个函数 $f(A)=\sum g(a_i)$ ，每个之和自己有关

$\sum g(a_i)=1+\sum \frac {a_i} m\sum_{j\ne i}\frac 1 {n-1}(\sum _{k\ne i,k\ne j}g(a_k)+g(a_j+1)+g(a_i-1))$

相当于枚举 $i\to j$ 。其他人 $k$ 不变。上面这个等式。

然后用A题中类似的待定系数法。

$$\sum_{a_i} \dfrac {a_i} m(g(a_i)-g(a_i-1))+\sum \dfrac {m-a_i}m\times \dfrac 1 {n-1}(g(a_i)-g(a_i+1))=1$$

上面的式子就是假如 $i$ 参与交换事件得到的等式（也可以看做上面那个式子的移项？）

为什么我感觉直接上差分法就行了？

$$\sum_{a_i} \dfrac {a_i} m((g(a_i)-g(a_i-1))+\dfrac {m-a_i}{a_i}\times \dfrac 1 {n-1}(g(a_i)-g(a_i+1)))=1$$

一个合法解显然是： $(g(a_i)-g(a_i-1))+\dfrac {m-a_i}{a_i}\times \dfrac 1 {n-1}(g(a_i)-g(a_i+1))=1$

增量法来做 $d_i$ 。

对于初始值直接代入 $d_1=0$ 就行。（ $d_1$ 可以任取，会得不同 $g$ ，但最后得出来是相同的）

F

因为和E题放在一起，而且感觉和E题挺像的。

假如我们钦定某种颜色为结束，那么只和当前球数量、总数量有关。

而一种球只要不消亡肯定是能走到终点的？

---

球的总数不变。

$f(A)-\sum f(A')=1$

$=\sum \frac {a_i}m\times \frac{m-a_i}{m-1}(g(a_i)-g(a_i+1))+\frac {m-a_i}m\times \frac {a_i}{m-1}(g(a_i)-g(a_i-1))$

$=\sum \frac{a_i}m\times \frac{m-a_i}{m-1}(2g(a_i)-g(a_i+1)-g(a_i-1))=1$

类比上题可得：

$\frac{m-a_i}{m-1}(2g(a_i)-g(a_i+1)-g(a_i-1))=1$

即：

$\frac {m-a_i}{m-1}(d(x+1)-d(x))=\frac {m-1}{m-a_i}$

直接令 $d_1=0$ 可以得到合法 $g_x$ 。

打表有 $g(M)=-n^2$ ，小的 $g$ 可以线性求。

$ans=\sum g(a_i)-g(M)$

---

我看的那份题解挺好懂的，我尝试复述一下解题过程

设 $f_i$ 表示当前有 $i$ 个赢的期望步数， $s$ 表示总球数。

令 $p$ 表示第一步抽到这个球，第二步不抽到这个球的概率（反过来是一样的），则有 $p=\frac{i(s-i)}{s(s-1)}$

然后显然有 $f_i=pf_{i+1}+pf_{i-1}+f_i(1-2p)+v$ ，其中 $v$ 表示当前赢的概率。因为我们需要操作一次，而期望为次数乘上概率，概率即为 $v$ 。

$v$ 的计算如下，设 $g_i=v$ ， 则：

• $g_0=0,g_s=1$

• $g_i=pg_{i+1}+pg_{i-1}+(1-2p)g_i$

• 移项可得： $g_i-g_{i-1}=g_{i+1}-g_i$

• 联立1式可得 $g_i=\frac i s$

我们现在有 $f_i=pf_{i+1}+pf_{i-1}+f_i(1-2p)+\frac i s$ ，化为同构式：

$$f_i-f_{i-1}=f_{i+1}-f_i+\dfrac{s-1}{s-i}$$

因为 $f_0$ 不存在，可得 $f_2=2f_1-1$ 。

因为 $f_s=0$ ，我们有

$$f_1=f_1-f_s=-\sum_{i=2}^s(f_i-f_{i-1})=(s-1)(f_1-f_2)+\sum_{i=2}^{s-1}\frac{s-1}{s-i}(s-i)=(s-1)(f_1-f_2)+(s-2)(s-1)$$

代入 $f_2=2f_1-1$ 可得：

$f_1=\frac{(s-1)^2}{s}$

此时 $f_1,f_2$ 已知，可递推出 $f_i$ 。答案即为 $\sum f_{a_i}$

G

大致意思就是，每天等概率一个 $a_i-1$ 。然后二分之一的概率生成一个新1，二分之一的概率按人数比例使一个 $a_i+1$ 。

---

如果没有第一个事件那么和前面那题几乎一样。

考虑 $f(A)-f(A')$ 每一个 $a_i$ 如何参与事件。

$$\sum\frac 1 2(g(a_i)-g(a_i-1)-g(1))\frac{a_i}m(+\frac 1 2(g(a_i)-g(a_i-1)-))$$

式子好乱，不想打了。大致就是要分讨首先被选的情况，然后是不被选的但有人加入的情况。

$\frac 1 2g_1+\sum$

然后套路化一轮， $d_1$ 随便代，就可以解出所有 $d$ ，解出所有 $g$

但是此题 $d_1$ 不能随便带，只能令 $d_1=-2$ 。因为 $1+\frac 1 2 d_1$ ，那样子就可以去到 $d_1$ 的影响？？？？？？？

考场是因为打表得？

---

比较厉害的一题，需要非常大胆。下面写的东西有些latex懒得打直接复制洛谷题解区的。

构造势能函数，根据常见结论， $f(0)=0$ ，答案为 $\sum f(a_i)-f(n)$ 。

考虑三种可能的转移情况：

• 自己新建一个 ： $\phi(A_{t + 1}) = \phi(A_t) - f(a_x) + f(a_x - 1) + f(1)$

• 回到原来组： $\phi(A_{t + 1}) = \phi(A_t)$

• 去到另一个组： $\phi(A_{t + 1}) = \phi(A_t) - f(a_x) + f(a_x - 1) - f(a_y) + f(a_y + 1)$

转移到下一步需要-1的期望步数，把上述根据概率汇总可得：

$$-1=\sum _{i = 1} ^m \dfrac {a_i} n \cdot \dfrac 1 2 \left(- f(a_i) + f(a_i - 1) + f(1) + \sum _{j = 1}^m [i\neq j] \dfrac {a_j} n \left( - f(a_i) + f(a_i-1) - f(a_j) + f(a_j+1)\right)\right)$$

整理得：

$$f(1) + 2 + \sum_i \dfrac{a_i}{n^2} (-(3n-2a_i)f(a_i)+(2n-a_i)f(a_i-1)+(n-a_i)f(a_i + 1)) = 0$$

为了消掉常数项，我们令 $f(1)=-2$ （也可以用pht打表做法）

再次整理的：

$$f(x+1)=\dfrac{3n-2x}{n-x}f(x)-\dfrac{2n-x}{n-x}f(x-1)$$

此时我们已经得到前两项 $f$ 及其递推公式了，但是 $\sum a_i\le 4\times 10^8$ ，我们要把 $\log$ 取得，直接采用分数表示：

$$f(x+1)=\dfrac{3n-2x}{n-x}\times \dfrac{d_1}{d_2}-\dfrac{2n-x}{n-x}\times\dfrac{s_1}{s_2}$$

整理得：

$$f(x+1)=\dfrac{(3n-2x)d_1s_2-(2n-x)s_1d_2}{(n-x)d_2s_2}$$

H

先梳理一下题意。

每次等概率选取两个集合的代表人，把一个加入到另一个集合里，把原先集合解散。由于人之间没有区别，相当于是对于 $a,b$ ，变成 $a-1$ 个 $1$ 和1个 $b+1$ 。每个集合都是等概率被选取的。

---

还是套路的：

$f(A)-\sum f(A')$

f(A)={∑1c(当前集合大小)(g(ai)−(ai−1)g1)1c(g(ai)−g(ai+1))=1f(A) = \begin{cases} \sum \frac 1 {c(\text{当前集合大小})}(g(a_i)-(a_i-1)g_1) \\ \frac 1 c (g(a_i)-g(a_i+1)) \end{cases}=1

让 $(g(a_i)-(a_i-1)g_1)+(g(a_i)-g(a_i+1))=1$ 即可。令 $g_1=$ 什么都行。

然后不知道在凑什么。

---

看了题解势能函数的做法，感觉势能函数真得是一个很巧妙的东西。

势能函数并没有任何实际意义，他只是一个符合一些性质而构造出来的特殊函数，而利用这个函数的一些性质我们能拿来处理一些事情。

在停时问题中，我们要求期望停止的步数，对于一个状态 $f(S)$ ，只需要满足以下性质就是一个好的 $f$ ：

1. $f(End)$ 无后继节点

2. $E(f(nxt_S)-f(S))=1$ ，也就是每走一步期望步数能加1。

因此 $f$ 是不唯一的。

首先 $S$ 的状态太大，我们可以先提一些关键信息提炼出来，比如 $f(x)$ 表示有 $x$ 个附属节点。

根据定义，答案即为 $f(n-1)-\sum f(a_i)$

考虑构造 $f$ ，第一个条件显然满足，第二个条件我们可以这么表示，考虑现在选的两个点分别有 $u,v$ 个附属节点，则有：

$$f(u)+f(v)+1=\frac 1 2(f(u+1)+vf(0))+\frac 1 2(f(v+1)+u(f0))$$

常见trick，设 $f(0)=0$

$f(u)+f(v)+1=\frac 1 2 (f(u +1)+f(v+ 1))$

根据同构思想，一种合法的 $f$ 为：

$$f(u)+\frac 1 2=\frac 1 2f(u + 1)$$

整理得 ：

$$f(u +1)=2f(u)+1$$

直接可得通项公式： $f(n)=2^n-1$ 。

I

题意很简洁，但我依然没思路，希望今天不要来多项式。毕竟3e5还是有点慌的。不过1e9+7感觉问题不大。

---

环长是1e9。只有差距有意义，而且加起来才有用。

f(A)−f(A′)={∑kn×1k(g(ai)−g(ai−1))+kn1k(g(ai)−g(ai−1)=1f(A)-f(A')= \begin{cases} \sum \frac k n \times \frac 1 k(g(a_i)-g(a_i-1)) \\ +\frac k n \frac 1 k(g(a_i)-g(a_i-1) \end{cases}=1

理论上会猜 $g(a_i)-g(a_i-1)+g(a_i)-g(a_i+1)=1$ ，但是 $k$ 有影响。

因为我们之前外面有 $\frac {a_i}m$ ，且他们的和为 $1$ ，但现在不是。

$g(x)-g(x-1)+g(x)-g(x+1)=\frac {nx}m$

$d(x)-d(x+1)=\frac {nx}m$ ，正常代入 $d_0$ 就行。

但此题要求 $\sum^Mg(1)$ .

因为差分是等差数列，所以 $d$ 是等差数列求和的结果。因此 $d$ 是个二次函数，然后也能打出 $g$ 。

---

还是停时。

少掉的球可以用 $f(0)=0$ 解决。

每个状态的势能是 $\sum f(d_i)$ ，答案就是 $\sum f(d_i)-f(m)$

考虑操作一步的影响：

$$\sum_{i=1}^{k} f(d_i)=1+\frac{1}{n}\sum_{i=1}^k (f(d_i+1)+f(d_{i+1}-1 )+\sum_{j=1,j\neq i,j\neq i+1}^k f(d_j))$$

化简并构造同构：

$$\left(\sum_{i=1}^{k} f(d_i)-\sum_{i=1}^k f(d_i-1)\right)=n+ \left(\sum_{i=1}^k f(d_i+1)-\sum_{i=1}^{k} f(d_i)\right)$$

换元 $g(x)=f(x)-f(x-1)$ ：

$$\sum_{i=1}^{k} g(d_i)=n+\sum_{i=1}^k g(d_i+1)$$

继续换 $h(x)=g(x+1)-g(x)$ （其实可以一次到位，但是不方便我们逆推）：

$$-n=\sum_{i=1}^{k} h(d_i)$$

由于 $\sum d_i=m$ ，我们可以构造一种合法的 $h(x)$ 满足：

$$h(x)=-\frac{nx}{m}$$

等差数列求和可逆推 $g$ ：

$$g(x)=-\frac{nx(x-1)}{2m}$$

为了方便逆推 $f$ ，我们改变一下 $g$ 的形式：

$$g(x) = -\frac{n}{m} \binom{x + 1}{2}$$

经典杨辉三角按列求和问题：

$$f(x) = -\frac{n}{m} \binom{x + 1}{3}$$

J

初三下讲过，但我当时没打，现在忘了。

---

不能用停时的原因，因为 $a_i$ 的状态总数太多了。因为球是不对称的。

---

我看的那份题解有点复杂，我看我能不能自己重新写一遍，毕竟我只是对着题解代码打了一遍而已

考虑当前所有值离 $A$ 的最大为 $i$ ，我们是可以直接记做 $f_i$ 的。这个很巧妙，因为理论上一个最大差值可以对应很多种情况，但现在直接归一了。为了证明其可行，我们只需要用转移方程说明即可。

我们找一个最大的 $r$ 满足 $a_r<i$ ，显然对于一个 $i$ 这个 $r$ 只有一个。

$$f_i=\frac 1 n(rf_{i-1}+\sum_{j>r}f_{a_j})+1$$

其实就是考虑下一步我按到哪，按到前面最大值-1，按到后面清0就成为新的最大差值。

现在方程式是从两个方向转移，移一下项可得：

$$f_{i-1}=\frac 1 r(n(f_i-1)-\sum_{j>r}f_{a_j})$$

我们的边界是 $f_0=0$ ，我们要求 $f_{a_N}$ ，但这个dp是从大往小的，于是我们考虑令： $g_i=f_{a_N}-f_i$ ，那么有：

$f_i=f_{a_N}-g_i$

$$f_{a_N}-g_{i-1}=\frac 1 r(n(f_{a_N}-g_i-1)-\sum_{j>r}(f_{a_N}-g_{a_j}))$$

整理得：

$$g_{i-1}=\frac 1 r(n(g_i+1)-\sum_{j>r}g_{a_j})$$

边界是 $g_{A_N}=0$ ，由于 $f_0=0$ ，因此我们求得 $g_0$ 即可，现在就符合顺序dp了。

但是我们发现状态数过大，因此我们要优化转移，记 $s_r=\sum_{j>r}g_{a_j}$ ，则：

$$g_{i-1}=\frac 1 r(n(g_i+1)-s_r)$$

考虑进行这样的变形（我验证了是成立的， 但怎么推出来的不太懂 ）：

$$g_{i-1}+\frac{N-s_r}{N-r}=\frac N r(g_i+\frac{N-s_r}{N-r})$$

这东西要怎么推呢？我们想要快速计算，其实就是要左右同构，回到这条式子：

$$g_{i-1}=\frac 1 r(n(g_i+1)-s_r)$$

既然我们希望同构，我们假设加上一个常数 $t$ ：

$g_{i-1}+t=\frac n r(g_i+1-\frac{s_r}N+\frac {rt}N)$

满足 $t=1-\frac{s_r}N+\frac{rt}N$ ，解得 $t=\dfrac{N-s_r}{N-r}$

此时我们就可以快速递推了：

$$g_{a_i}+\frac{N-s_r}{N-r}=(\frac N r)^{a_{i+1}-a_i}(g_{a_{i+1}}+\frac{N-s_r}{N-r})$$

记 $h_i=g_{a_i}$ ，直接列出转移式子：

$$h_i=(\frac N r)^{a_{i+1}-a_i}(h_{i+1}+\frac{N-s_r}{N-r})-\frac{N-s_r}{N-r}$$

其中 $h_N=0$ ， $h_0$ 即为答案。

非常厉害，从第一步转化，到中间改变方向，加减常数这些技巧真得太厉害了。