T25:Matching

1）题目意思

有 N 个男生、N 个女生。给你一个 N×N 的 0/1 矩阵 a[i][j]：

• a[i][j]=1 表示男 i 可以和女 j 配对
• a[i][j]=0 表示不能配对

要把所有人配成 N 对（每个男生、每个女生都恰好出现一次），问一共有多少种配对方法，答案对 1e9+7 取模。

---

2）思路解析（状态压缩 DP：计数完美匹配）

N<=21，可以用二进制 mask 表示“哪些女生已经被配走”。

按男生顺序一个个匹配：

• 当 mask 里有 k 个 1，说明已经给前 k 个男生配完了女生
• 下一个要处理的男生编号就是 k+1

定义：

• dp[mask]：当已经使用的女生集合为 mask 时的配对方案数（默认男生按顺序处理）

转移：

• 设当前要处理的男生为 i = popcount(mask) + 1
• 枚举一个还没用过的女生 j
  • 如果 a[i][j]=1，就可以配对
  • dp[mask | (1<<j)] += dp[mask]

初始：

• dp[0]=1（还没配任何人）

答案：

• dp[(1<<N)-1]

复杂度：

• 状态数 2^N，N=21 时约 200 万
• 每个状态最多枚举 N 个女生
• 总体可过

---

3）代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD=1000000007LL;                          // 取模常数

int main(){                                                // 主函数入口
    ios::sync_with_stdio(false);                           // 加速输入输出
    cin.tie(nullptr);                                      // 加速输入输出

    int N;                                                 // 人数N
    cin>>N;                                                // 读入N

    static int a[21][21];                                  // a[i][j]表示男i和女j是否可配（0/1）
    for(int i=0;i<N;i++){                                  // 读入矩阵
        for(int j=0;j<N;j++){                              // 读入矩阵
            cin>>a[i][j];                                  // 读入a[i][j]
        }
    }

    int FULL=(1<<N)-1;                                     // FULL表示所有女生都已使用的状态

    static long long dp[1<<21];                            // dp[mask]表示当前状态的方案数
    for(int mask=0;mask<=FULL;mask++)dp[mask]=0;           // 初始化dp为0
    dp[0]=1;                                               // 初始：一个都没配，方案数为1

    for(int mask=0;mask<=FULL;mask++){                     // 枚举所有mask
        long long cur=dp[mask];                            // 取出当前方案数
        if(cur==0)continue;                                // 为0跳过

        int i=__builtin_popcount((unsigned)mask);           // i表示已经配了多少个男生（也是下一位男生的下标）
        if(i>=N)continue;                                   // 如果已经配完N个男生就无需转移

        for(int j=0;j<N;j++){                              // 枚举女生j
            if(mask&(1<<j))continue;                       // 如果女生j已被使用则跳过
            if(a[i][j]==0)continue;                        // 如果男(i+1)不能配女(j+1)则跳过
            int nmask=mask|(1<<j);                         // 新状态：把女生j加入已使用集合
            dp[nmask]+=cur;                                // 累加方案数
            dp[nmask]%=MOD;                                // 取模
        }
    }

    cout<<dp[FULL]%MOD<<endl;                              // 输出答案
    return 0;                                              // 程序结束
}