AtCoder Beginner Contest 321

一言:
只要你在，我便无所不能。
——进击的巨人

感觉只有最后一道题有点意思，其他的就是时间问题，但是速度还是不够快，思维要跟上啊。

有意思的是，周考考了回退背包，这里居然又来一次。。

\(\text{G : Electric Circuit}\)

这个期望又是拿来唬人的，直接状压得到所有的连通块具体包含了哪些点，然后算概率，加起来就是答案。

首先先预处理每个状态中，在 \(a\) 数组中出现了多少次，在 \(b\) 数组中出现了多少次，假设为 \(num1[statu],num2[statu]\)。

首先，如果 \(num1[statu] \not = num2[statu]\)，显然这个连通块是构造不出来的。

然后，我们只考虑 \(num1[statu]\) 和 \(num2[statu]\) 这些点。首先有一个乱排的总方案 \(num1[statu]!\)。但是显然有一些方案是不合法的，它会使得这个连通块不完整，所以要减去这些方案。

考虑从前面的状态转移的到这个减去的方案。先枚举状态 \(k\)，显然满足 \(k\) 是 \(statu\) 的子状态。那么显然，如果你将 \(k\) 状态中的所有 \(num1[k]\) 与 \(num2[k]\) 完全匹配，那么就会使得 \(k\) 这个连通块被独立出来，然后对于其他剩下来的，乱排就可以了，故要减去 \(\sum dp[k] \times (num1[statu]-num1[k])!\)。

减完之后，统计答案的时候，由于只考虑了 \(num1[statu],num2[statu]\) 这些点，所以要将 \(dp[statu]\) 乘上 \((m-num1[statu])!\)，也就是其他边乱排。

最后乘个逆元就行了。

\(\text{Submission}\)

\(\text{What I learned}\)

• AT 的期望全是唬人的，就是把所有状态的贡献加上就行了。

• 有些时候，为了减去不合法的方案，这些方案数可能可以从其他合法的子状态中转移得到。