AC题解

思路说明
题目要求：从 M 个集合中选出至少一个集合，使得它们的并集恰好覆盖 1..N 的所有元素。求有多少种选法。

关键约束
N ≤ 10，M ≤ 10，数据范围极小。

这意味着我们可以使用状态压缩（位掩码）来高效表示集合和并集。

算法步骤
将每个集合转换为位掩码

每个元素 x（1 ≤ x ≤ N）对应二进制中的第 x-1 位。

例如 N=3，元素 1 → 第0位（001），元素 2 → 第1位（010），元素 3 → 第2位（100）。

集合 {1,2} 的掩码 = (1<<0) | (1<<1) = 011（二进制）= 3。

枚举所有非空子集

共有 2^M - 1 种非空子集（用整数 sub 从 1 到 (1<<M)-1 表示）。

对每个 sub，遍历 M 个集合，若 sub 的第 i 位为 1，则把该集合的掩码按位或到 cover 中。

最终 cover 表示当前子集所有集合的并集。

判断是否全覆盖

全覆盖的掩码应为所有 N 位都是 1：full = (1<<N) - 1。

若 cover == full，则当前子集符合要求，答案加 1。

输出答案。

复杂度分析
枚举子集：O(2^M)

对每个子集计算并集：O(M)

总复杂度 O(2^M * M)，当 M=10 时约 10,240 次操作，非常快。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> masks(M, 0);
    for (int i = 0; i < M; ++i) {
        int C;
        cin >> C;
        for (int j = 0; j < C; ++j) {
            int x;
            cin >> x;
            masks[i] |= 1 << (x - 1);  // 元素1对应第0位
        }
    }
    
    int full = (1 << N) - 1;
    int ans = 0;
    // 枚举所有非空子集
    for (int sub = 1; sub < (1 << M); ++sub) {
        int cover = 0;
        for (int i = 0; i < M; ++i) {
            if (sub >> i & 1) {
                cover |= masks[i];
            }
        }
        if (cover == full) {
            ++ans;
        }
    }
    
    cout << ans << endl;
    return 0;
}