[HNOI2011] 卡农

题意

有 n 个音阶，一个音乐片段是若干个音阶组成的非空集合。现在要选出 m 个互不相同的片段，片段顺序不计，并要求每个音阶总共出现偶数次。求方案数。

思路

把每个片段看成一个 n 位二进制向量：某一位为 1 表示包含这个音阶。每个音阶出现偶数次，等价于选出的所有向量异或和为 0。

朴素做法是在小数据下枚举所有非空集合，再枚举其中大小为 m 的子集检查异或和。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <bits/stdc++.h>
using namespace std;

// brute.cpp：枚举所有非空音阶集合的子集，只适合 n,m 很小的验证。

int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    int total = (1 << n) - 1;
    long long answer = 0;
    for (int mask = 0; mask < (1 << total); mask++) {
        if (__builtin_popcount((unsigned)mask) != m) {
            continue;
        }
        int xor_sum = 0;
        for (int i = 0; i < total; i++) {
            if (mask & (1 << i)) {
                xor_sum ^= (i + 1);
            }
        }
        if (xor_sum == 0) {
            answer++;
        }
    }
    cout << answer << '\n';

    return 0;
}

设非空向量总数为：

text

1S = 2^n - 1

令 f[i] 表示有序选择 i 个互不相同的非空向量，且异或和为 0 的方案数。最后答案要除以 m!，因为题目不区分片段顺序。

为了递推 f[i]，先任意有序选择前 i-1 个不同非空向量，方案数是 P(S,i-1)。若总异或和要为 0，第 i 个向量会被前面向量的异或和唯一确定。

这个唯一确定的向量可能非法：

它是空向量：说明前 i-1 个向量异或和已经为 0，有 f[i-1] 种；
它与前面某个向量重复：指定重复的是前面第几个向量，再删掉这一对相同向量，剩下 i-2 个向量异或和仍为 0。数量为 (i-1) * (S-i+2) * f[i-2]。

所以：

text

1
2f[0] = 1
f[i] = P(S,i-1) - f[i-1] - (i-1)*(S-i+2)*f[i-2]

最终答案：

text

1f[m] / m!

模数 10^8+7 是质数，除法用阶乘逆元实现。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77#include <bits/stdc++.h>
using namespace std;

const long long MOD = 100000007LL;
const int MAXN = 1000005;

long long n, m;
long long factorial[MAXN];
long long inverse_factorial[MAXN];
long long ordered_count[MAXN]; // ordered_count[i] 表示有序选择 i 个不同非空集合且异或和为 0 的方案数。

long long fast_power(long long a, long long b) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) {
            result = result * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    if (m > (1LL << min(n, 20LL)) - 1 && n <= 20) {
        cout << 0 << '\n';
        return 0;
    }

    long long total_non_empty = fast_power(2, n) - 1;
    if (total_non_empty < 0) {
        total_non_empty += MOD;
    }

    factorial[0] = 1;
    for (int i = 1; i <= m; i++) {
        factorial[i] = factorial[i - 1] * i % MOD;
    }
    inverse_factorial[m] = fast_power(factorial[m], MOD - 2);
    for (int i = (int)m; i >= 1; i--) {
        inverse_factorial[i - 1] = inverse_factorial[i] * i % MOD;
    }

    ordered_count[0] = 1;
    long long perm_prefix = 1; // P(total_non_empty, i-1)，先任意选前 i-1 个不同非空集合。
    for (int i = 1; i <= m; i++) {
        // 最后一个集合由前 i-1 个集合的异或和唯一决定。
        long long bad_equal_zero = ordered_count[i - 1];
        long long bad_duplicate = 0;
        if (i >= 2) {
            long long remain_choice = (total_non_empty - (i - 2)) % MOD;
            if (remain_choice < 0) {
                remain_choice += MOD;
            }
            bad_duplicate = (long long)(i - 1) * remain_choice % MOD * ordered_count[i - 2] % MOD;
        }
        ordered_count[i] = (perm_prefix - bad_equal_zero - bad_duplicate) % MOD;
        if (ordered_count[i] < 0) {
            ordered_count[i] += MOD;
        }
        long long next_factor = (total_non_empty - (i - 1)) % MOD;
        if (next_factor < 0) {
            next_factor += MOD;
        }
        perm_prefix = perm_prefix * next_factor % MOD;
    }

    long long answer = ordered_count[m] * inverse_factorial[m] % MOD;
    cout << answer << '\n';

    return 0;
}

复杂度

时间复杂度 $O(m + log n)$ 。

空间复杂度 $O(m)$ 。

总结

这题的关键转换是“偶数次出现”等价于二进制向量异或和为 0。递推时先让最后一个向量由前缀唯一确定，再扣掉空向量和重复向量两类非法情况。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

代码

复杂度

总结

一图流解析