跳转至

P3214 [HNOI2011] 卡农 题解

题意

给定正整数 \(n,m\),你需要从 \(\{1,2,\cdots n\}\) 集合中选出 \(m\) 个互不相等的非空子集,并且 \(1\sim n\) 的每个元素都在选出的集合中总共出现了偶数次。求选择的方案数对 \(10^8+7\) 取模的结果。

题解

题意等价于你需要选择 \(m\)\(n\) 位二进制数,满足

  1. 数字都不为 \(0\)
  2. \(m\) 个数字互不相同;
  3. \(m\) 个数字的异或和为 \(0\)

记值域大小 \(k=2^n-1\)

显然我们可以钦定 \(m\) 个子集组成的序列有序,然后将最终结果除以 \(m!\)。我们注意到,由于异或和为 \(0\) 的限制,选择了前 \(m-1\) 个元素之后,第 \(m\) 个元素就唯一确定了。现在我们尝试去掉重复和空的方案。

\(f_i\) 表示 \(m=i\) 时的答案。前 \(i-1\) 个元素的总方案数为 \(\binom{k}{i-1}\),此时第 \(i\) 个元素已经唯一确定为前面数字的异或和。

尝试去掉不满足 \(1\) 的方案数,容易发现,当 \(a_i=0\) 当且仅当前 \(i-1\) 个数字构成一组异或和为 \(0\) 的合法方案,因此方案数为 \(f_{i-1}\)

尝试去掉不满足 \(2\) 的方案数,由于前 \(i-1\) 个数字都互不相等,因此考虑 \(a_i\) 和前面的 \(a_j\) 相等的情况。当我们固定 \(j\) 之后,剩下的 \(i-2\) 个数又构成一组合法方案,方案数为 \(f_{i-2}\)。同时,\(j\)\(i-1\) 种不同的取值,\(a_i\)\(a_j\)\(k-i+2\) 种不同的取值,都和另外 \(i-2\) 个数的方案独立,因此总方案数为 \((i-1)(k-i+2)f_{i-2}\)

因此,转移如下:

\[ f_i=\binom{k}{i-1}-f_{i-1}-(i-1)(k-i+2)f_{i-2} \]

时间复杂度 \(O(m)\)

AC 代码
#include<iostream>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
const int MOD = 1e8 + 7;

int n, m, k;
int inv[N], fact[N], chs[N];

int f[N], ans;

inline int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = (ll)res * a % MOD;
        a = (ll)a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {

    cin >> n >> m;

    k = qpow(2, n) - 1;
    fact[0] = inv[1] = chs[0] = 1;
    for(int i = 1; i <= m; i++) fact[i] = (ll)fact[i - 1] * i % MOD;
    for(int i = 2; i <= m; i++) inv[i] = MOD - (ll)(MOD / i) * inv[MOD % i] % MOD;
    for(int i = 1; i <= m; i++) chs[i] = (ll)chs[i - 1] * (k - i + 1) % MOD * inv[i] % MOD;

    f[0] = 1;
    f[1] = 0;
    for(int i = 2; i <= m; i++) {
        f[i] = (ll)chs[i - 1] * fact[i - 1] % MOD - f[i - 1] - (ll)f[i - 2] * (i - 1) % MOD * (k - i + 2) % MOD + 2 * MOD;
        f[i] %= MOD;
    }

    ans = f[m];
    for(int i = 1; i <= m; i++) ans = (ll)ans * inv[i] % MOD;

    cout << ans << '\n';

    return 0;
}