P3214 [HNOI2011] 卡农题解

题意

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

题解

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

数字都不为 \(0\)；
\(m\) 个数字互不相同；
\(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;
}

P3214 [HNOI2011] 卡农 题解

题意

题解

P3214 [HNOI2011] 卡农题解