BZOJ2339【HNOI2011】卡农 <计数DP+组合数学>

Problem

【HNOI2011】卡农

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128MB}$

Description

Input

Output

Sample

标签：计数DP

Solution

考试时没想出来，不过听了觉得挺简单的。

首先把每个片段看成一个数，每个音阶看成该数的一位，则每位为$0$或$1$，题意可以转化为求在$1\sim 2^n-1$中选$m$个数使其异或和为$0$的方案数。我们先不考虑无序性，求出所有排列后除$m!$即为答案。

设$f[i]$为选$i$个数的方案数，考虑先选$i-1$个数，最后一个数即为前面的数的异或和，这样才能使总异或和位$0$。那么如果不考虑限制，直接选则有$P_{2^n-1}^{i-1}=(2^n-1)\times (2^n-2)\times (2^n-3)\times \cdots \times (2^n-i+1)$种选法。

只可能有两种不合法的情况，即最后一个数位$0$或最后一个数在前面$i-1$个数种出现过。对于第一种情况，不合法方案数为选$i-1$个数的合法方案数，即为$f[i-1]$。而对于第二种情况，去掉相同的数后，其他数异或和为$0$，这样就有$f[i-2]$中方案，而去掉的数的位置有$i-1$种选法，去掉的数的值有$2^n-1-(i-2)$种选法，故共会去掉$f[i-2]\times (i-1)\times (2^n-i+1)$种不合法方案。

于是，$\mathrm{DP}$方程为

f[i]= \begin{cases} \ \ \ \ \ \ \ \ \ \ \ \ 1 &\mbox{$(i=0)$}\\ \ \ \ \ \ \ \ \ \ \ \ \ 0 &\mbox{$(i=1)$}\\ (2^n-1)\times (2^n-2)\times \cdots \times (2^n-i+1)-f[i-1]-f[i-2]\times (i-1)\times (2^n-i+1) &\mbox{$(i\ge 2)$} \end{cases}

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
#define MOD 100000007
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;    lnt p, q, c, f[MAX_N+5], g[MAX_N+5], inv[MAX_N+5] = {1LL, 1LL};
void init(int n) {for (int i = 2; i <= n; i++) inv[i] = (MOD-MOD/i*inv[MOD%i]%MOD)%MOD;}
int main() {
    read(m), read(n), init(n), p = f[0] = c = 1LL, f[1] = 0LL, g[1] = 1LL;
    for (int i = 1; i <= m; i++) (p *= 2) %= MOD; (p += MOD-1) %= MOD, q = p;
    for (int i = 2; i <= n; i++, (q += MOD-1) %= MOD) g[i] = g[i-1]*q%MOD;
    for (int i = 2; i <= n; i++) f[i] = (g[i]-(f[i-1]+1LL*(i-1)*(p-i+2)%MOD*f[i-2]%MOD)%MOD+MOD)%MOD;
    for (int i = 1; i <= n; i++) (c *= inv[i]) %= MOD;	return printf("%lld", f[n]*c%MOD), 0;
}