Luogu P3214 [HNOI2011] 卡农 题解

媒介

标题传送门 Luogu P3214 [HNOI2011] 卡农 。
非常吃头脑的一道题。
题意

有 \(n\) 个元素构成的聚集，现从中无序地选取 \(m\) 个互不雷同的非空子集，且每个元素出现偶数次，求方案数，对 \(10^8+7\) 取模。
思绪

思量 dp 。我们逐个思量选取的子集，于是界说 \(dp_i\) 为思量到第 \(i\) 个子集的合法方案数。那么我们先来思量什么样的方案是合法的。

• 选取的 \(i\) 个子集互不雷同；
  
• 选取的 \(i\) 个子集全都非空；
  
• 选取的 \(i\) 个子会合每个元素出现偶数次。
  

显然条件 \(3\) 是最严格的，我们从它来入手。不难发现，假如已经选了 \(i-1\) 个子集，为了满意条件 \(3\) ，第 \(i\) 个子集的选取是唯一的。这里产生了 \(P_{2^n-1}^{i-1}\) 种方案。为什么用分列数而非组合数？由状态界说决定。假如用组合数，我们就无法界说 “第 \(i\) 个” 。
接下来思量条件 \(2\) 。显然由分列公式得到的前 \(i-1\) 个子集都黑白空的。我们只需思量第 \(i\) 个是否为空。联合条件 \(3\) ，我们发现，第 \(i\) 个子集为空，当且仅当前 \(i-1\) 个子集满意了全部条件。那么这里要减去 \(dp_{i-1}\) 种方案。
末了来思量条件 \(3\) 。又显然由分列公式得到的前 \(i-1\) 个子集都是互不雷同的。我们只必要思量第 \(i\) 个子集是否与前面的某个雷同。设第 \(i\) 个子集与第 \(j\) 个雷同，轻易留意到从当火线案里去掉这两个子集，剩余的 \(i-2\) 个子集仍旧满意全部条件。思量 \(j\) 有 \(i+1\) 种大概的取值，且子集 \(i,j\) 有 \(2^n-1-(i-2)\) 种大概的选法，以是这里要减去 \(dp_{i-2}(i-1)(2^n-i+1)\) 种方案。这也表明了为什么总方案数用分列而非组合：只有当思量序次时，\(j\) 的取值才故意义。
综上，我们写出状态转移方程：

\[dp_i = P_{2^n-1}^{i-1} - dp_{i-1} - dp_{i-2}(i-1)(2^n-i+1)\]
留意几点：
<ol>留意到 \(2^n-1\) 很大，而 \(i-1\) 不大，以是分列数可接纳递推求得。有 \(P_{2^n-1}^i = P_{2^n-1}^{i-1}\cdot (2^n-i)\) 。

dp 显然应该从 \(3\) 开始。不难发现当 \(m>= 1;        }        return res;}void init() {        fac[0] = P[0] = 1;        pw = qpow(2, n);        for(int i=1; i>n>>m;        init();        for(int i=3; i