题目描述
有 $n$ 个点，点 $i$ 和点 $j$ 之间可以连 $0\sim c_{i,j}$ 条无向边。求连成一张无向连通图的方案数模 $10^9+7$ 。
两个方案不同，当且仅当：存在点对 $(i,j$ ，使得 $i$ 与 $j$ 之间的边数不同。
输入
标准输入。输入第一行包含一个正整数n，表示珠子的个数。接下来n行，每行包含n个非负整数，用空格隔开。这n行中，第i行第j个数为ci,j。
输出
标准输出。输出一行一个整数，为连接方案数对1000000007取模的结果。
样例输入
3
0 2 3
2 0 4
3 4 0
样例输出
50
题解
状压dp+容斥原理
和 【bzoj3456】城市规划 的前半部分方法类似，用总连边方案数减去不连通方案数得到连通方案数。
但是在本题中点与点是不同的，因此采用状压dp的方法来解决。
设 $f_i$ 表示 $i$ 集合的点连成无向连通图的方案数，$g_i$ 表示 $i$ 集合的点连成无向图的方案数。
预处理出 $g_i$ ，根据定义得 $g_i=\prod\limits_{j.k\in i,j<k}(c_{j,k}+1)$ 。
然后求 $f_i$ 。用总方案数 $g_i$ 减去不连通的方案数。枚举 $i$ 集合中编号最小的点（$i\&(-i)$）所在连通块的集合 $j$ ，减去 $f_jg_{i-j}$ 。
故状态转移方程为： $f_i=g_i-\sum\limits_{j\subsetneqq i,(i\&(-i))\in j}f_jg_{i-j}$ 。
最后的答案就是 $f_{2^n-1}$ 。
时间复杂度 $O(2^n·n^2+3^n)$
#include <cstdio>
#define mod 1000000007
typedef long long ll;
ll c[20][20] , f[65540] , g[65540];
int main()
{
int n , i , j , k;
scanf("%d" , &n);
for(i = 0 ; i < n ; i ++ )
for(j = 0 ; j < n ; j ++ )
scanf("%lld" , &c[i][j]);
for(i = 0 ; i < (1 << n) ; i ++ )
{
g[i] = 1;
for(j = 0 ; j < n ; j ++ )
for(k = 0 ; k < j ; k ++ )
if(i & (1 << j) && i & (1 << k))
g[i] = g[i] * (c[j][k] + 1) % mod;
f[i] = g[i];
for(j = i & (i - 1) ; j ; j = i & (j - 1))
if(j & (i & -i))
f[i] = (f[i] - f[j] * g[i ^ j] % mod + mod) % mod;
}
printf("%lld\n" , f[(1 << n) - 1]);
return 0;
}