题目

Solution

关于dp：

题意可以转换为：给出一个的无向图，边有边权。定义一个子图的权值为所有边权的乘积，问所有使全部 n n n个点连通的图的权值和为多少
f [ s ] f[s] f[s]表示当前联通状态为 s s s，
g [ s ] g[s] g[s]表示选 s s s的状态的点，连通性任意的方案数
那么 g [ s ] = <munder> ∏ i , j ∈ s </munder> ( a [ i ] [ j ] + 1 ) g[s]=\prod_{i,j∈s}(a[i][j]+1) g[s]=i,j∈s∏​(a[i][j]+1)
f [ s ] = g [ s ] − <munder> ∑ 编 号 最 小 的 点 ∈ j , j ⊊ s </munder> f [ j ] g [ s − j ] f[s]=g[s]-\sum_{编号最小的点∈j,j⊊s}f[j]g[s-j] f[s]=g[s]−编号最小的点∈j,j⊊s∑​f[j]g[s−j]
= &gt; f [ s ] = g [ s ] − <munder> ∑ 编 号 最 小 的 点 ∉ j , j ! = ∅ , j ⊆ s </munder> g [ j ] f [ s − j ] =&gt;f[s]=g[s]-\sum_{编号最小的点∉j,j!=∅,j⊆s}g[j]f[s-j] =>f[s]=g[s]−编号最小的点∈/​j,j!=∅,j⊆s∑​g[j]f[s−j]
其实不一定要编号最小，但是编号最小的点最容易取

关于子集枚举：
for (i=s;i;i=(i-1)&s)
  • 正确性：
    首先，因为有&s，所以 i i i一定是 s s s的子集
    其次，因为每次 i i i只减 1 1 1，所以一定能枚举完 s s s的子集（具体不想讲了，二进制的东西讲起来麻烦，而且只要自己随便找个数模拟一下就好了）
  • 复杂度：
    T = ∑ i = 0 n ( i n ) 2 i − 1 T=\sum_{i=0}^n (^n_i)2^{i-1} T=∑i=0n​(in​)2i−1（ i i i表示 s s s中 1 1 1的个数）
    &lt; ∑ i = 0 n ( i n ) 2 i = ∑ i = 0 n ( n − i n ) 2 i = ( 1 + 2 ) n = 3 n &lt;\sum_{i=0}^n (^n_i)2^i=\sum_{i=0}^n(^n_{n-i})2^i=(1+2)^n=3^n <∑i=0n​(in​)2i=∑i=0n​(n−in​)2i=(1+2)n=3n

Code

#include<bits/stdc++.h>
using namespace std;
int n,i,j,f[1<<16],g[1<<16],a[16][16],s,M=1e9+7;
int main(){
	scanf("%d",&n);
	for (i=0;i<n;i++)
		for (j=0;j<n;j++) scanf("%d",&a[i][j]),a[i][j]++;
	for (s=0;s<1<<n;s++){
		f[s]=1;
		for (i=0;i<n;i++) if (s&(1<<i))
			for (j=i+1;j<n;j++) if (s&(1<<j)) f[s]=1ll*f[s]*a[i][j]%M;
		g[s]=f[s];
		for (i=j=s^(s&-s);j;j=(j-1)&i) f[s]-=1ll*g[j]*f[s^j]%M,f[s]+=f[s]<0?M:0;
	}
	printf("%d",f[(1<<n)-1]);
}