leetcode.5387. n个匹配方案数(状压dp)

5387. 每个人戴不同帽子的方案数

设表示前个帽子状态为的合法方案数，表示里这些人是否戴了帽子的集合。
那么对于第个帽子,要么只有一个人戴，要么没有人戴。

所以对于合法的第个人戴这个帽子或者没有人戴。

没有人戴这个帽子。

合法的第个人戴这个帽子。

复杂度

class Solution {
public:
    int g[43][11];
    int dp[42][1025]={0};
    const int mod=1e9+7;
    int numberWays(vector<vector<int>>& hat) {
        int n=hat.size();
        for(int i=0;i<n;i++){
            for(int j:hat[i])
            g[j][i]=1;
        }
        dp[0][0]=1;
        for(int i=1;i<=40;i++){
            for(int j=-1;j<n;j++){
                for(int k=0;k<(1<<n);k++){
                    if(j==-1)dp[i][0|k]=dp[i-1][k];
                    else{
                        if(g[i][j]&&!(1<<j&k)){
                            dp[i][1<<j|k]+=dp[i-1][k];
                            dp[i][1<<j|k]%=mod;
                        }
                    }
                }
            }
        }
        return dp[40][(1<<n)-1];
    }
};