Description：

给一个无向图，点 $i$ 和点 $j$ 之间有 $c_{i,j}$ 条边，问有多少种选边的方案使得图联通。

$1\leqslant n\leqslant16$

Solution：

连通图计数的经典套路，设 $F[S]$ 表示集合 $S$ 中的点可以不连通的方案数， $G[S]$ 表示必须联通的方案数，那可以用不一定联通的减去一定不联通的，不一定连通的方案数 $\begin{align}F[S]=\prod_{i,j\in S}(c_{i,j}+1)\end{align}$ ，然后枚举第一个点所在集合有哪些点，注意为了防止重复必须枚举第一个点所在的集合，设为 $S'$ ，剩下的可以连通也可以不连通，但第一个点所在集合必须全部连通，所以 $G[S]=F[S]-G[S']\times F[\complement_SS']$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 17

int n;

int f[1 << MAXN],g[1 << MAXN];

#define MOD 1000000007

int c[MAXN][MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= n;++j)

			scanf("%d",&c[i][j]);

	int tot = (1 << n) - 1;

	for(int b = 0;b <= tot;++b)f[b] = 1;

	for(int b = 0;b <= tot;++b)

		for(int i = 1;i <= n;++i)

			for(int j = i + 1;j <= n;++j)

				if((b & (1 << (i - 1))) && (b & (1 << (j - 1))))

					f[b] = 1ll * f[b] * (c[i][j] + 1) % MOD;

	for(int b = 0;b <= tot;++b)

	{

		g[b] = f[b];

		for(int k = b;k != 0;k = (k - 1) & b)

		{

			if((k & 1) == 0)continue;

			if(k == b)continue;

			g[b] = (g[b] - 1ll * g[k] * f[b ^ k] % MOD + MOD) % MOD;

		}

	}

	cout << g[tot] << endl;

	return 0;

}