P3214 [HNOI2011] 卡农
题意：\(m\) 个集合，\(n\) 种元素，求集合间互不相同且每种元素出现偶数次的方案数。
题目等价于从 \(1 \sim 2^n - 1\) 里选出 \(m\) 个不同的数，使他们异或和为 \(0\)。
不妨对每个数标号，由于互不相同，最后除以 \(m!\) 即可。
设 \(f_i\) 表示前 \(i\) 个数异或和为 \(0\) 的合法方案数。
显然 \(a_i = \bigoplus_{j = 1}^{i - 1} a_j\)，对于前 \(i - 1\) 个数的每种选法都唯一对应一个 \(a_i\)，即 \(f_i \gets (2^n - 1)^{\underline{i - 1}}\)。
非法方案有两种：
-
\(a_i = 0\)。等价于 \(\bigoplus_{j = 1}^{i - 1} a_j = 0\)，即 \(f_{i - 1}\)。
-
\(a_i\) 等于某个 \(a_j\ (j < i)\)。
也就是剩下的 \(i - 2\) 个人异或和为 \(0\)，对应 \(f_{i - 2}\)。
枚举 \(j\) 的位置和 \(a_j\) 是哪个，乘上 \((i - 1) \times (2^n- i + 1)\) 的系数。
评黑确实不够格。submission
P3330 [ZJOI2011] 看电影
P6620 [省选联考 2020 A 卷] 组合数问题
P3160 [CQOI2012] 局部极小值
P3270 [JLOI2016] 成绩比较
P7213 [JOISC2020] 最古の遺跡 3
【清华集训2014】主旋律
P2595 [ZJOI2009] 多米诺骨牌
弃疗。