P3214 Solution
为了方便，我们求有序的答案最后再除掉 \(m!\)。
题目的限制包括：
-
每种元素总共出现偶数次
-
不存在相同的两个集合
-
没有空集
考虑偶数的限制，你发现每个集合中元素出现次数要么 \(0\) 要么 \(1\)。
于是如果你确定了前 \(m-1\) 个集合，最后一个集合会被唯一确定。
我们先确定前 \(m-1\) 个集合，这里方案数是 \(A_{2^n-1}^{m-1}\)，因为要保证这 \(m-1\) 个集合非空且不重。
但是这样无法保证最后一个集合非空且和前面不重。我们考虑减去不合法的方案。
如果最后一个集合空了，把它去掉，前 \(m-1\) 个集合仍然满足所有三条限制。
如果设 \(dp_{i}\) 为 \(i\) 个集合的答案，这部分要减去的就是 \(dp_{m-1}\)。
最后限制一下最后一个集合不与前面的重复，因为前面的集合已经互不相同了，我们假设 \(m\) 与 \(i\) 相同。
把 \(m\) 和 \(i\) 去掉，这部分的元素去掉了 \(2\) 次，于是剩下的集合会满足题目的三条限制。
这部分要减去的方案即为 \((m-1)(2^n-1-(m-2))dp_{m-2}\)。
\(m-1\) 表示 \(i\) 有 \(m-1\) 种选法，\(2^n-1-(m-2)\) 表示集合 \(m\) 和 \(i\) 的形态，且要和其他 \(m-2\) 个集合不同。
最后转移式即
\[dp_{m}=A_{2^n-1}^{m-1}-dp_{m-1}-(m-1)(2^n-1-(m-2))dp_{m-2} \]\(\mathcal O(m)\) 求解即可。
标签：限制,最后,solution,p3214,减去,集合,去掉,dp From： https://www.cnblogs.com/iorit/p/18046097