2022/04/09 做题记录

CF464D

每个装备期望相同，于是可以只考虑一种装备，最后将答案乘上 k 即可，设 dp[i][j] 表示还剩 i 轮，目前装备等级为 j 的答案的期望，容易转移（抽到 1~j 可以一起转移），问题在与 j 可以达到 n ，但发现一个装备升到 n 级所需要的次数的期望是 $O(n^2)$ 级别的，于是可以忽略 $j \ge 1000$ 的情况，时间复杂度 $\text{O}(1000*n)$ = $\text{O}(n)$ (???)

code: /code/2022.4.9/CF464D.cpp

P3773

用卢卡斯定理可以证明 ${n \choose k}$ 是奇数当且仅当 n&k==k，因为拆成二进制后只有 ${0 \choose 1}=0$。

于是可以直接 dp。

code: /code/2022.4.9/P3773.cpp

P4284

只考虑子树内的情况很容易转移：$a'=a+(1-a)*b$ ，其中 $b$ 是 dp[son]*p[edge],接下来我们再进行一次 dfs，假设我们 dfs 到一个点的时候它的祖先的 dp 值已经是真正的答案了，那么我们就想用上边那个式子将它的父亲合并进来，但我们需要去除它的父亲中它自己提供的贡献，可以发现 $(1-b)*a = a'-b$，于是 $a = \frac{a'-b}{1-b}$，（因为这个过程的本质就是把不同的 b 合并到 a 里来，显然合并顺序无关紧要）特殊情况就是 $b=1$，但这种情况下说明这个点通电的概率就是 1，所以不用考虑父亲也行。

code: /code/2022.4.9/P4284.cpp