组合计数中，如何求解概率期望的Solution Set？

本文共计3455个文字，预计阅读时间需要14分钟。

主要是真正的数字水平低于人均。而且效率略有降低，不像写点简单题目解答。实际上是集训拉题单。AGC005D，一眼容积猜疑，将冲破变成边缘的形状，位置连边构成干燥链。选择一条边就成““

主要是真的数数水平低于人均啊。

而且效率有点小低，不如写点简略题解。

其实是集训拉的题单。

AGC005D

一眼容斥，将冲突看成边的形式，位置连边构成若干链。选择一条边就是一个冲突。

然后每个链可以单独考虑生成函数然后卷起来，或者每个链直接做 DP。

motivation: 容斥，然后就很自然。

AGC026D

有一个关键观察是一行确定之后上下两行的颜色可以大致确定（要么唯一，要么因为下面红蓝相间所以可以填两种红蓝相间的）。

然后可以 DP。记 \(dp_{i,0/1}\) 表示（多叉）笛卡尔树上第 \(i\) 个结点的方案数/最后一行红蓝相间的方案数。这样往下面的转移比较好表示。

motivation: 贡献形式不同的只有两种。

UOJ310 ※

先写出每个巧克力的形式幂级数，指数采用异或的方式，系数带 \(2\)，大概长成 \((1+2x^{a_i})\)。答案就是 \(x^0\) 的系数。

利用 xor-FWT 的定义式 \(b_i = \sum_j (-1)^{|i \cap j|} a_j\) 大概看得出来每一项单独 FWT 后系数只有 \(-1\) 和 \(3\)，然后和的 FWT 就是 FWT 的和……那就全加起来 FWT 解出每一项 \(-1\) 和 \(3\) 的个数 \(p,q\)，然后该项就是 \((-1)^p 3^q\)，最后 IFWT 回去就好了。

motivation: FWT 定义式及系数观察。