下次再见 题解

· · 个人记录

计算 ans 等于每个起始位置期望的和．最后除以 n．

brute

枚举起点．

由期望的线性性，可以计算每个位置的贡献．设 E_i 表示 i 位置点击时的期望得分．那么有

E_i=3P_{i,0}+P_{i,1}+0.5P_{i,2}

考虑设 F_{i,j(j<K)} 表示之前不存在 K 次连续 miss，从起点到 i 位置，i 位置向后连续的 miss 次数为 j 的方案数．令 F_{i,K} 表示在 i 之前死掉的概率．有转移

\begin{aligned} &F_{i,j}\times P_{miss}(i+1)\rightarrow F_{i+1,j+1} &(j<K)\\ &F_{i,j}\times (1-P_{miss}(i+1))\rightarrow F_{i+1, 0} &(j<K)\\ &F_{i,K}\rightarrow F_{i+1,K} \end{aligned}

对于计算答案有

ans=\sum_{i=0}^{n-1}(1-F_{i,K})E_{i+1}

时间复杂度为 O(n^2K)．

特殊性质 A

## 特殊性质 $B

由于 p_{i,3} 只有 0 和 100 两种取值，那么从任意一个位置 i 开始可以游玩的区间是固定的．即从 i 开始到第一个 p_{j,3} 为 100 的位置之前结束．我们预处理每个位置得分期望的前缀和既可以快速计算答案．

100\%

和 brute 同样拆分贡献．先考虑固定起点位 1．

设 F_i 表示刚好在 i 处死掉的概率，G_i 表示在 i 处还没死的概率，P_i 表示在 i 处 miss 的概率．有

\begin{aligned} &F_i=(\prod_{i-K+1\le j\le i}P_j)(1-P_{i-K})G_{i-K-1}\\ &G_i=1-\sum_{j\le i} F_j \end{aligned}

那么起点为 1 的答案就是

\sum_{i=0}^{n-1} G_iE_{i+1}

考虑多起点．我们将 F,G 拓展为 F_{sta,i},G_{sta, i}．设 H_i=\sum_{sta\le i}G_{sta,i}

同样是拆分贡献．我们枚举每个造成贡献的位置，然后枚举起点，那么有

ans=\sum_{i=0}^{n-1}(H_i+1)E_{i+1} \begin{aligned} H_i&=\sum_{sta\le i}G_{sta,i}\\ &=\sum_{sta\le i}(1-\sum_{sta\le j\le i}F_{sta,j})\\ &=i-\sum_{sta\le i}\sum_{sta\le j\le i}F_{sta,j}\\ &=i-\sum_{j\le i}\sum_{sta\le j}F_{sta,j} \end{aligned}

那么问题变为了对于每一个 i 求 \sum_{sta\le i}F_{sta,i}．

分类讨论：

F_{sta,i}= \begin{cases} &0 &(sta> i-K+1)\\ &\prod_{i-K+1\le j\le i}P_j &(sta=i-K+1)\\ &(\prod_{i-K+1\le j\le i}P_j)(1-P_{i-K}) &(sta=i-K)\\ &(\prod_{i-K+1\le j\le i}P_j)(1-P_{i-K})G_{sta} &(sta<i-K) \end{cases}

前三类直接算，第四类发现把前面的系数 (\prod_{i-K+1\le j\le i}P_j)(1-P_{i-K}) 提出来后，后面的东西全部加起来是 H_{i-K-1}．

复杂度为 O(n\log w)．瓶颈在计算逆元．

发现前缀积每一位置上的逆元可以预处理：1/(\prod p_{i,3})=\prod(1/p_{i,3})，而本质不同的 p_{i,3} 不超过 100 种．

总时间复杂度降为 O(n)．