牛客35627C - Card 链接：https://ac.nowcoder.com/acm/contest/35627/C 知识点：概率期望 难度：蓝 题意 有 C 张金卡，S 张禁卡，B 张炸弹卡。 现在不放回地抽卡， 若取到金卡则继续抽卡， 若取到禁卡则立即停止抽卡， 若取到炸弹卡，则清空之前取到的所有金卡并立即停止抽卡。 求抽卡停止时，取到金卡数量的期望。 思路 考虑期望的线性可加性。 什么是期望的线性可加性？ E=事件1对期望的贡献×P1+事件2对期望的贡献×P2+事件3对期望的贡献×P3+...+事件n对期望的贡献×PnE=事件1对期望的贡献\times P_1+事件2对期望的...

牛客33785F - 到底是多少分啊 链接：https://ac.nowcoder.com/acm/contest/33785/F 知识点：组合数学，古典概型，计数DP，前缀和优化DP 难度：紫 题意 给出一个长度为 nnn 的数列，现在需要执行以下的操作 KKK 次： 选择数列中的某个数字，给它加上 111 操作完以后会产生很多不同的数列，现在从中随机挑选一个数列。 问该数列所有元素乘积的期望。 思路 错误思路： 考虑每种情况对答案的贡献，将贡献累加就是最终答案。 计算每种情况对答案的贡献太复杂，比如:先将 a1a_1a1​ 加上1，再将 a2a_2a2​ 加上1，和先将 a2a_2...

牛客7745C - 数学考试 链接：https://ac.nowcoder.com/acm/contest/7745/C 知识点：组合数学,容斥,计数DP 难度：紫 题意 求 1∼n1∼n1∼n 的排列，有 mmm 个限制条件， 第 iii 个限制条件表示前 P[i]P[i]P[i] 个数不能是 P[i]P[i]P[i] 的排列， 求符合要求的排列的个数。 思路 考虑线性容斥。 初步思路： 假设 P[i]={3,5,7}P[i]=\lbrace 3,5,7 \rbraceP[i]={3,5,7} 前 333 个数字 是 333 的排列的方案数 =3!=3!=3! 那么整个数列 前 ...