CCSP2021T2抽卡题解

1.同时记录SSR和SR数量 $O(n^3m)$

使用 $dp[t][SSR][SR]$ 维护手中已经有 $t$ 种SSR时的期望，后二维用于记录SSR和SR卡的数量，用于计算答案。

$dp[0][0][0]=\sum \limits_{SSR=2}^N \sum \limits_{SR=0}^{N-SSR}{dp[2][SSR][SR] \times \frac{p_i}{3}}$

$dp[0][0][SR]=\sum\begin{cases}dp[0][0][SR-1] \times q_i &\text{SR}\\ dp[0][0][SR] \times (1-q_i-p_i) &\text{R}\end{cases}$

$dp[1][SSR][SR]=\sum\begin{cases}dp[0][SSR-1][SR] \times p_i &\text{新SSR} \\ dp[1][SSR-1][SR] \times \frac{p_i}{3} &\text{已有SSR}\\ dp[1][SSR][SR-1] \times q_i &\text{SR}\\ dp[1][SSR][SR] \times (1-q_i-p_i) &\text{R}\end{cases}$

$dp[2][SSR][SR]=\sum\begin{cases}dp[1][SSR-1][SR] \times \frac{2p_i}{3} &\text{新SSR} \\ dp[2][SSR-1][SR] \times \frac{2p_i}{3} &\text{已有SSR}\\ dp[2][SSR][SR-1] \times q_i &\text{SR}\\ dp[2][SSR][SR] \times (1-q_i-p_i) &\text{R}\end{cases}$

2.仅记录SSR数量，同时维护SR贡献 $O(n^2m)$

用 $dp[t][SSR]$ 维护有 $t$ 种SSR时的期望，同时用 $dpSR[t][SSR]$ 维护SR卡对答案的贡献。

$dp[0][0]=\sum \limits_{SSR=2}^N{dp[2][SSR] \times \frac{p_i}{3}}$

$dp[1][SSR]=\sum\begin{cases}dp[0][SSR-1] \times p_i &\text{新SSR} \\ dp[1][SSR-1] \times \frac{p_i}{3} &\text{已有SSR}\\ dp[1][SSR] \times (1-p_i) &\text{SR和R}\end{cases}$

$dp[2][SSR]=\sum\begin{cases}dp[1][SSR-1] \times \frac{2p_i}{3} &\text{新SSR} \\ dp[2][SSR-1] \times \frac{2p_i}{3} &\text{已有SSR}\\ dp[2][SSR] \times (1-p_i) &\text{SR和R}\end{cases}$

$dpSR[t][SSR]=\sum\begin{cases}dpSR[t-1][SSR-1] \times \frac{(3-t+1)p_i}{3} &\text{新SSR} \\ dpSR[t][SSR-1] \times \frac{t \cdot p_i}{3} &\text{已有SSR}\\ dp[t][SSR] \times q_i &\text{SR}\\ dpSR[t][SSR] \times (1-q_i-p_i) &\text{R}\end{cases}$

3.不记录卡的数量，只维护贡献 $O(nm)$

不再记录SSR的数量，而是直接维护其对答案的贡献，每当SSR数量增加一，$E((K+1)^2)=E(K^2)+E(2K)+E(1)$，所以要同时维护右边的三个期望。

用 $dp[t]$ 维护有 $t$ 种SSR时的期望，$dpSR[t]$ 维护SR卡的贡献，对于SSR卡的贡献，用 $dpSSR1[t]$ 维护 $E(2K)$ 的期望，$dpSSR2[t]$ 维护 $E(K^2)$ 的期望。

$dp[0]=\sum\begin{cases}dp[0] \times (1-p_i) &\text{SR和R} \\ dp[2] \times \frac{p_i}{3} &\text{新SSR}\end{cases}$

$dp[1]=\sum\begin{cases}dp[0] \times p_i &\text{新SSR} \\ dp[1] \times \frac{p_i}{3} &\text{已有SSR}\\ dp[1] \times (1-p_i) &\text{SR和R}\end{cases}$

$dp[2]=\sum\begin{cases}dp[1] \times \frac{2p_i}{3} &\text{新SSR} \\ dp[2] \times \frac{2p_i}{3} &\text{已有SSR}\\ dp[2] \times (1-p_i) &\text{SR和R}\end{cases}$

$dpSR[t]=\sum\begin{cases}dpSR[t-1] \times \frac{(3-t+1)p_i}{3} &\text{新SSR} \\ dpSR[t] \times (1-\frac{t \cdot p_i}{3}) &\text{已有SSR和R}\\ dp[t] \times q_i &\text{SR}\end{cases}$

$dpSRR1[t]=\sum\begin{cases}(dpSRR1[t-1]+2dp[t-1]) \times \frac{(3-t+1)p_i}{3} &\text{新SSR} \\ (dpSRR1[t]+2dp[t]) \times \frac{t \cdot p_i}{3} &\text{已有SSR}\\ dpSSR1[t] \times (1-p_i) &\text{SR和R}\end{cases}$

$dpSRR2[t]=\sum\begin{cases}(dpSRR2[t-1]+dpSSR1[t-1]+dp[t-1]) \times \frac{(3-t+1)p_i}{3} &\text{新SSR} \\ (dpSRR2[t]+dpSSR1[t]+dp[t]) \times \frac{t \cdot p_i}{3} &\text{已有SSR}\\ dpSSR2[t] \times (1-p_i) &\text{SR和R}\end{cases}$

$ans=\sum\begin{cases}ans &\text{答案自身累加} \\ (dpSRR2[2]+dpSSR1[2]+dpSR[2]+dp[2]) \times \frac{p_i}{3} &\text{新SSR}\end{cases}$

4.利用矩阵乘法进行维护 $O(n+m)$

将上一步当中的状态转移改为矩阵形式，除去 $dpSSR1[0],dpSSR2[0]$ 两个恒为0的状态，共有11个状态，成为秩为11的矩阵。

最终动态规划过程为 $S \times A_1 \times A_2 \times \cdots \times A_n \times T$，其中 $S$ 为第一个元素为1其余为零的行向量，$T$ 为最后一个元素为1其余为零的列向量，$A_i$ 是根据转移方程和对应 $p_i,q_i$ 得到的矩阵。因为矩阵乘法的结合律，只要先预处理出 $SL[i],SR[i]$ ，表示从 $S \times A_1 \times \cdots \times A_i$ 和 $A_i \times \cdots \times A_n \times T$ 的向量，当询问更改第 $t$ 次抽卡的概率，只要计算 $SL[t-1] \times A_t^{'} \times SR[t+1]$ 即可。

如果用直接用矩阵相乘，复杂度为 $11^3$ ，因为状态可以直接用向量表示，所以直接维护向量乘积。