社区讨论

警示后人:为什么不能直接去掉零除以2求得方案数

P3067[USACO12OPEN] Balanced Cow Subsets G参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mj9yqd3u
此快照首次捕获于
2025/12/17 20:03
3 个月前
此快照最后确认于
2025/12/20 11:20
3 个月前
查看原帖

因为看到讨论版有和我一样做错的,遂警示后人

为什么不能直接去掉零除以2求得方案数?如果我们分开两部分来求,对于两部分如果都不为空,设第一部分方案数为P(A)P(A),第二部分为P(B)P(B)
那么我们就会对P(A)P(A)进行2P(B)2P(B)次累加,因为划分子集左右会重复计算,而我们希望得到P(A)×P(B)P(A)\times P(B)。到这里直接除以二还是没有问题的。
但是对于包含空集的部分,我们设空集以外的两部分方案数为P(A),P(B)P(A),P(B)。那么我们计算的方案数实际上是(2P(A)+1)×(2P(B)+1)=4P(A)P(B)+1+2P(A)+2P(B)(2P(A)+1)\times (2P(B)+1)=4P(A)P(B)+1+2P(A)+2P(B)
但我们实际上想求的是P(A)+P(B)+P(AB)P(A)+P(B)+P(AB)
所以不能混合在一起算,每部分要自己单独算。

回复

1 条回复,欢迎继续交流。

正在加载回复...