本题解搬运自苏博文（本题出题人，来自清华大学），非常简略，代码看不懂思密达，想看代码的自己去翻官方配置。

题目简述

抽 $n$ 次卡，每次以已知的概率抽出 SSR/SR/R ；SSR由三种，每次抽到 SSR 随机获得一种（可重复获得）。

每当抽齐三种 SSR ，进行一次结算，收益为 $S^2+K$ 其中 $S,K$ 分别为 SSR SR 张数；结算后清空抽到的卡

多次结算收益累加，求总收益的期望；此外需要应对 $m$ 次假设性修改概率。

算法 1：暴力 $O(5^nm)$

枚举 $n$ 次抽卡中，每次抽到的是 R SR 和 SSR 中的哪一种，统计概率和收益

15(+5)pts

算法 2：DP $O(n^3m)$

通过树状图求概率时，我们会注意到 如果两个状态有相同的 SSR种类数 SSR个数 SR个数 则这两个状态之后的贡献相同，可以看作一个。

维护相应状态的出现概率，每次抽卡就是状态间的转移；诸状态总数为 $3\times n^2$ ，每个状态 $n$ 次转移，单次 $O(1)$

25(+5)pts

算法 3：DP $O(n^2m)$

合并不同的SR个数为相应的期望。

35(+5)pts

算法 4：DP $O(nmd)$

合并SSR的个数，此时需要维护 个数平方的期望，在抽到SSR时通过期望维护： $E((x+1)^2)=E(x^2)+2E(x)+1$

记状态数为 $d$ $d$ 约为15

HINT：$t\leq 100$

修改只在前面出现，后续的转移是相同的，不应当每次计算一遍

预处理出100次后状态和最终状态的线性关系。

复杂度 $O((n+mt)d)$

算法 5：矩阵乘法 $O((n+m)d^3)$

注意到状态之间的转移是线性的，固化转移，形成矩阵（方阵），记矩阵的秩为 $d$ （std 中 $d=13$）

记录矩阵前缀积和后缀积，每次修改时计算三个矩阵乘法。

算法 6：优化 $O((n+m)d^2)$

把前缀和后缀矩阵改成向量进行存储，每次转移时根据当前抽卡的 $p_i,q_i$ 构建对应矩阵，转移时利用矩阵乘以向量运算即可。

给分的子任务分布

• 纯暴力： 10-15pts （写不写待修改 - 重跑）
• $n^3$ DP: +20pts （画状态树，合并状态，用期望代替具体值）
• $n^2$ DP： +10pts （将一部分贡献也化作期望）
• $nm$ DP： +20pts （平方的期望 $E((x+1)^2)=E(x^2)+2E(x)+1$，还有一定分类计算的难度）
• 预处理转移: +15pts （注意到状态转移是线性的）
• 矩阵乘法 $d^3$ ： +10-15pts (取决于是否将 $S^2$ 和 $K$ 分离计算，常数)
• 乘上首尾向量 $d^2$ : 100pts