description
给定 \(n,m\leq 10^6\)，求 \(m\) 个互不相同的非空集合，每个集合的元素都是 \([1,n]\) 中的正整数，且每个正整数在所有集合里出现的次数均为偶数的方案数。（集合之间无序）
solution
感觉很妙的 dp 和组合。
不妨先不考虑集合之间无序，因为每个集合互不相同，最后答案除以一个 \(m!\) 就可以了。
设 \(f_i\) 表示 \(i\) 个合题意的集合有序的方案数。
先来考虑一个问题，现有 \(a\) 个集合，如果想再加一个集合，使得这些集合符合要求，该怎么加新的集合？
首先如果这 \(a\) 个集合已经符合要求，那么显然我们无法找到一个非空集合，使得加上它之后的 \(a+1\) 个集合还满足要求 (1)；如果 \(a\) 个集合互不相同且存在元素出现奇数次，可以把这 \(a\) 个集合里所有出现奇数次的数放到这个新的集合里，如果这个新的集合在前 \(a\) 个集合里出现过，则不可能做到 (2)；否则，这个新的集合即符合要求 (3)。
于是我们可以得出转移：
-
\(f_1=f_2=0\)
-
\(f_i=(i-1)!\dbinom{2^n-1}{i-1}-f_{i-1}-(2^n-i+1)(i-1)f_{i-2}\)
注意第二个转移式，我们用所有可能的方案减去不合法的方案。其中 \(f_{i-1}\) 对应第 (1) 个不合法情况；\((2^n-i+1)(i-1)f_{i-2}\) 对应第 (2) 个不合法的情况，\(2^n-i+1\) 是 \(2^n-1-(i-2)\) 的结果，表示有多少个集合可以作为这个重复的集合，\(i-1\) 是这个重复的集合在原先前 \(i-1\) 个集合里是在哪个位置的方案数。
代码实现时注意到 \(\dbinom{2^n-1}{i-1}\) 中 \(i-1\) 不大，可以直接计算组合数。