DP Training O 简单状压DP

DP Training O 简单状压DP

题意

有(N)个女士和男士，给出一个(N imes N)的矩阵表示(i)号男士和女士可以配对，问最终配成(N)对的方案数

[1 leq N leq 21 ]

分析

看数据范围很容易想到状压DP

(dp[i][S])表示当前到第(i)个男士，女士的选择情况为(S)，方案数是多少

其中(a_{i,j-1} = 1)

[dp[i][S] += dp[i - 1][S xor (1 << j)] ]

注意到(i)的大小就是(S)中(1)的数量，因此不需要枚举(i)

复杂度变为(O(n imes 2^n))

代码

ll dp[1 << maxn];
int a[maxn][maxn];

int main(){
	int n = rd();
	for(int i = 0;i < n;i++)
		for(int j = 0;j < n;j++)
			a[i][j] = rd();
	dp[0] = 1ll;
	for(int i = 1;i < (1 << n);i++){
		int now = num(i) - 1;
		for(int j = 0;j < n;j++)
			if(i & (1 << j) && a[now][j]) {
				dp[i] += dp[i ^ (1 << j)];
				dp[i] %= MOD;
			} 
	}
	cout << dp[(1 << n) - 1];
}