Solution - P3214 [HNOI2011] 卡农

Posted on Edited on

P3214 [HNOI2011] 卡农

打表找规律失败了。。。

参考题解第一篇。

其实就差一步的思路。

题意简化：每次在 [1,2n−1][1,2^n-1] 中选一个数，选 mm 次，不可重复选，使得这 mm 个数的异或和为 00 ，求方案数（最后答案数除以 m!m! ）。

令 fmf_m 表示选 mm 次的方案数。我们尝试得出 ff 的递推式。

首先，不考虑重复，答案是 A2n−1m−1A_{2^n-1}^{m-1} （最后一个数由前 m−1m-1 个数决定）。设前 mm 个数的异或和为 kk 。接下来看两种违法情况：

  1. k=0k=0

要减去前 m−1m-1 个数的异或和为 00 的方案数。

解决方案：答案减去 fm−1f_{m-1} 。

  1. kk 在前 m−1m-1 个数中出现过

这意味着前 m−1m-1 个数中除去等于 kk 的那个数的另外 m−2m-2 个数的异或和为 00 。我们把等于 kk 的数拎出来，剩下的 m−2m-2 个数异或和为 00 的可能情况数就是 fm−2f_{m-2} 。由于前 m−2m-2 个数和等于 kk 的那个数是互异的，故 kk 的可能取值只有 2n−1−(m−2)=2n−m+12^n-1-(m-2) = 2^n-m+1 种。这个时候我们再把 kk 放回剩下的 m−2m-2 个数，插空的方法有 m−2+1=m−1m-2+1 = m-1 种。根据乘法原理，这三者之积就是我们多算的方案数。

解决方案：答案减去 fm−2⋅(2n−m+1)⋅(m−1)f_{m-2}\cdot (2^n-m+1)\cdot (m-1) 。

故递推式为：

fm=A2n−1m−1−fm−1−fm−2⋅(2n−m+1)⋅(m−1)f_m = A_{2^n-1}^{m-1} - f_{m-1} - f_{m-2}\cdot (2^n-m+1)\cdot (m-1)

最终答案为：

ans=fmm!ans = \frac{f_m}{m!}

由于 108+710^8+7 是个质数，我们可以用费马小定理求出 (m!)−1(m!)^{-1} 。 A2n−1iA_{2^n-1}^{i} 可以预处理。

总复杂度 O(n+m+log⁡MOD)=O(n+m)O(n+m+\log MOD) = O(n+m) 。

这道题告诉我们，当我们发现当前方案好像会有不合法的部分时，不要着急放弃该方案，而要想一想能否容斥。像这种递推式较为复杂的题，打表找规律也没法找了。