题意：

一个无向图，n个点，m条边，要求删掉m-n条边使得图任然连通，问方案数。

 

思路：

留下n条边，相当于一个树+一条边，这样就有一个唯一的环。

枚举这个环并看成一个点，就相当于做生成树计数

1、找环

　　s是一个二进制状态，u为s中编号最小的点

　　dp[s][v] 以u为起点，经过s中所有的点，并以u结尾的路径有多少条

　　这样的环如果u,v有直接的边相连，再加上dp[s][v]里的路径，就可以得到若干个环

　　每个环顺时针被算一次，逆时针被算一次，所以要除以2

2、生成树计数

　　构造基尔霍夫矩阵，环中的点看成一个点

　　这样可能会有重边，必须要保留，基尔霍夫矩阵可以计算重边的情况

　　高斯消元的时候不是实数 要取模

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N = 17;const int S = 1<
        

ch[S+2];inline void add(ll& x, ll y){ x += y; if (x >= mod) x -= mod; if (x < 0) x += mod;}inline ll gcd(ll p, ll q){ ll r; while (q){ r = p%q; p = q; q = r; } return p;}inline ll fpow(ll x, int n){ ll ret = 1; while (n){ if (n&1) ret = ret*x%mod; x = x*x%mod; n >>= 1; } return ret;}inline void prepare(){ lim = 1<

st[s] && (!(s&t[v])) && g[u][v]){ dp[s|t[v]][v] += dp[s][u]; } } for (int s=0; s

=3){ int u = st[s]; for (int i=0; i

>= 1; num[s] %= mod; }}ll gauss(ll a[][N+5], int n){ for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j] = a[i][j]%mod; ll ret = 1; for (int i=2; i<=n; i++){ for (int j=i+1; j<=n ;j++) while (a[j][i]){ // 类似与辗转相除的消元 ll t = a[i][i]/a[j][i]; for (int k=i; k<=n; k++) add(a[i][k], -t*a[j][k]%mod); for (int k=i; k<=n; k++) swap(a[i][k], a[j][k]); ret = -ret; } if (!a[i][i]) return 0; ret = ret*a[i][i]%mod; } return (ret+mod)%mod;// for (int i=1; i<=n; i++)// for (int j=1; j<=n; j++){// if (a[i][j]<0) a[i][j] += mod;// }// ll ret = 1, val = 1;// for (int i=1; i