1 条题解

  • 0
    @ 2026-11-12 21:57:47

    [O] Matching(dp_o)题解

    题意简述

    NN 男 NN 女,ai,j=1a_{i,j}=1 表示可配对。求完美匹配方案数  mod 109+7\bmod 10^9+7。

    思路

    关键想法:按女士顺序决策,用 bitmask 记录男士占用情况

    如果按"男士/女士各挑"的二维状态,需要 2N×2N2^N \times 2^N,不可行。注意到:按女士编号 1,2,…,N1,2,\dots,N 依次配对时,前 kk 位女士已经用掉了恰好 kk 位男士,所以只需记录"哪些男士被占用"。

    状态 fmaskf_{\text{mask}} = 用 mask 中的男士与前 popcount(mask)\text{popcount}(\text{mask}) 位女士配对的方案数。

    转移:设当前要配第 w=popcount(mask)−1w = \text{popcount}(\text{mask}) - 1 位女士(0 起),枚举 mask 中的男士 mm:

    $$f_{\text{mask}} \mathrel{+}= f_{\text{mask} \setminus \{m\}} \quad \text{当 } a_{w,m} = 1.$$

    答案 ffullf_{\text{full}}。

    为什么正确

    按女士顺序配对避免了重复计数:每个完美匹配都唯一对应一条"第 11 位女士选谁、第 22 位选谁…"的路径。

    复杂度

    时间 O(2N⋅N)O(2^N \cdot N),N=21N=21 时约 4.4×1074.4\times10^7,可过;空间 O(2N)O(2^N)。

    参考代码

    #include <cstdio>
    #include <vector>
    using namespace std;
    
    const long long MOD = 1000000007LL;
    
    int main() {
        int n;
        scanf("%d", &n);
        vector<vector<int>> a(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) scanf("%d", &a[i][j]);
        int full = 1 << n;
        vector<long long> f(full, 0);
        f[0] = 1;
        for (int mask = 1; mask < full; mask++) {
            int w = __builtin_popcount(mask) - 1;
            long long s = 0;
            for (int m = mask; m; m &= m - 1) {
                int man = __builtin_ctz(m);
                if (a[w][man]) s += f[mask ^ (1 << man)];
            }
            f[mask] = s % MOD;
        }
        printf("%lld\n", f[full - 1]);
        return 0;
    }
    

    易错点

    1. w 的取值:popcount(mask) - 1,因为 mask 表示"已占用,用于前 popcount 位女士",当前正在配第 popcount-1 位(0 起)。
    2. 每次 s 累加后要取模,否则 221×2^{21}\times 大数会溢出。
    3. 状态数组 221×82^{21} \times 8 B =16= 16 MB,可接受;用 int 则 8 MB。
    4. 全 0 矩阵的答案是 00(样例 3 的 N=1N=1)。

    数据说明

    共 17 组:4 组官方样例(含 N=21N=21 的 102515160102515160);N=1N=1 的 0/10/1;N=2N=2 全 1 与单位阵;N=5/8/10/12N=5/8/10/12 随机;N=16,20N=16,20 随机;N=21N=21 的全 1 矩阵(答案 21! mod p21! \bmod p)与随机矩阵(满规模)。

    • 1

    信息

    ID
    24
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者