首先我们先简化一下题意。为什么呢？因为这个题如果不简化题意是不太好做的
我们考虑用二进制表示集合，这样题意为：有\(2^n - 1\)个数，我们要从中选一个大小为\(m\)的无序子集，满足以下条件：
-
集合中所有数的异或和为\(0\)
-
集合中元素不可重复
首先无序子集是吓人的，因为我们可以先考虑出有序的情况，再直接\(/ m!\)即可
对于多种很严格的限制的题，我们要么考虑固定一个限制计算方案数，再减去在这个限定下包含其他限定的不满足条件的；要么考虑所有的方案数，再减去不满足条件的。这题目前我只知道前者的做法。
在这题中，我们如果固定了第\(2\)中限制，那第一种限制就很难维护了，因为这些数的值域很大，我们如果想要\(dp\)的话不好记录状态。因此我们考虑限制第\(1\)个条件
具体的，我们设\(dp_i\)表示我们已经固定了集合的前\(i\)个数，满足两个限制条件的方案数
我们发现如果我们限制第\(1\)个条件，有\(A_{2^n-1}^{i-1}\)，意思就是说对于前\(i-1\)个数从\([1,2^n-1]\)中随便选，然后让第\(i\)个数选\(\oplus_{j=1}^{i-1}{a_j}\)即可满足条件……等等，还没有结束。我们发现这样可能会出现第\(i\)个位置填\(0\)的情况，因此我们还要减去第\(i\)个位置填\(0\)，及\(- dp_{i-1}\)
然后我们考虑怎么减去第\(2\)个条件限制，我们设前\(i-1\)个数中有一个数\(j\)和\(i\)相同，则剩下\(i-2\)个数依然满足条件，因此我们要减去\(dp_{i-2} \times (i-1) \times (2^n - 1 - (i - 2))\)，其中\(2^n - 1 - (i - 2)\)的意思是第\(i\)个数和第\(j\)个数的可能的值的方案数
因此得到递推式：
\[dp_i = A_{2^n-1}^{i-1} - dp_{i-1} - dp_{i-2} \times (i-1) \times (2^n - 1 - (i - 2)) \]最终答案即为\(\frac{dp_m}{m!}\)
标签：满足条件,限制,个数,我们,P3214,HNOI2011,times,卡农,dp From： https://www.cnblogs.com/fox-konata/p/17701378.html