正题

题目链接:

题目大意

$n$ 个点的一张无向图，求所有联通子图的权值乘积和

解题思路

因为 $n$ 很小，考虑状压

设

f_i

表示点集为

i

时的方案数，我们发现正着做十分麻烦，考虑容斥。

首先定义

mul_i

表示点集

i

的所有子图的方案数，那么显然有

mul_i=\prod^{x,y\in i,x<y}(a_{x,y}+1)

枚举一个集合

s

有转移方程，选出一个点

p

一定在联通图内，这里状压为只有一个点

p

的集合

f_s=mul_s-\sum_{i\in (s-p)}f_{i+p}*mul_{s-p-i}

时间复杂度

O(3^n)

$c o d e$

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;const ll N=17,XJQ=1e9+7;ll n,mul[1<
      
       <
       
        >i)&1))continue;			mul[s]=mul[s^(1<
        
         >i)&1)&&((s>>j)&1)) mul[s]=mul[s]*(a[i][j]+1)%XJQ; break; } } mul[0]=0; for(ll s=1;s
         
          =0;j=(j==0?-1:((j-1)&i))) f[s]=(f[s]-f[j+p]*mul[i-j]%XJQ+XJQ)%XJQ; } printf("%lld",f[MS-1]);}