小明の雜貨鋪

The 2024 ICPC Asia Nanjing Regional Contest (The 3rd Universal Cup. Stage 16: Nanjing)

参考： https://codeforces.com/blog/entry/45223 https://www.cnblogs.com/znpdco/p/18172429 〇 引入 题意 起初有一个数字 000，每一秒钟随机选择一个数字与手上的数字作按位或。选择数字 iii 的概率是 pip_ipi​。问期望多少秒后，手上的数字变成 2n−12^n-12n−1。( 洛谷 P3175 [HAOI2015] 按位或) 分析 二进制 nnn 位数字每一位都要变成 1，先分开考虑，求每一位变成 1 的期望时间，然后再合并。但每种情形并不独立，相加后需要减去一些，有点容斥原理的感觉。 考虑 Min-Max 反演的期望形式。 设 xix_{i}xi​ 表示第 iii 个二进制位变为 1 的期望时间，SSS 是所有 xix_{i}xi​ 的集合，那么 E⁡[min⁡(S)]\operatorname{E}[\min(S)]E[min(S)] 表示某个集合 TTT 中 有一个 位置变成 1...

引入 有三件物品可供选择，物品甲重量为 3，物品乙重量为 8，物品丙重量为 5。有一个背包，问选择任意件物品放入背包后，背包总重为 8 的方案数。 列出所有的可能： 选甲，选乙，选丙； 选甲，选乙，选丙； 选甲，选乙，不选丙； 选甲，不选乙，选丙； 选甲，不选乙，不选丙； 不选甲，选乙，选丙； 不选甲，选乙，不选丙； 不选甲，不选乙，选丙； 不选甲，不选乙，不选丙。 每个物品 X 都有两种状态：选 X 或不选 X，而且每个物品的状态相互独立，直接用一个式子表达： （选甲 或 不选甲）且（选乙 或 不选乙）且（选丙 或 不选丙） 这个逻辑表达式包含了上面全部八种情形。这里 且 的含义是，如果 A 且 B，那么 A 必须执行，B 也必须执行。 把物品重量一并列入上面的表达式中： （重量为 3 或 重量为 0）且（重量为 8 或 重量为 0）且（重量为 5 或 重量为 0） 这样写虽然能表达所有的情况，但文字太多还是太麻烦了。希望选取一些数学符号，完全转化为数学表达式。 观察这个式子： （重量为 3 或 重量为 0）且（重量为 8 或...