Description

Solution

城市规划想必都做过，求无向连通图的个数

这题的思路是类似的
设$G[S]，F[S]$分别表示选取了S中的点所有图的c的乘积的和，以及连通图的c的乘积的和。

$G[S]$可以简单$O(2^n*n^2)$预处理
对于F，考虑总的减去不连通的，枚举编号最小/最大的点所在的连通块，令其为i，有转移
$F[S]=G[S]-\sum\limits_{P\subset S,i\in P}F[P]G[S-T]$

直接枚举子集是$O(3^n)$的，无法通过本题。
考虑优化

首先由于我们只需要知道全集的答案，因此我们需要知道的所有的F必然包含i
这样我们把i这一维剔除，那么$i\in P$的限制就没了

此时容易发现，这是一个子集卷积问题。（即集合$X,Y$会贡献到$X\cup Y$当且仅当$X\cap Y=\emptyset$）

快速沃尔什变换FWT有and,or,xor卷积，能不能做到子集卷积呢?
答案是肯定的

我们多记一维表示这个状态中1的个数
$f[i][S]$有意义当且仅当$S$中1的个数为i
那么$f[i][X]$和$f[j][Y]$一定会贡献到$f[i+j][X\cup Y]$，我们只需要在计算$f[i+j][S]$的时候将所有1的个数不为i的$S$的位置全部设为0即可。

对g也可以一样做。
按照从1的个数少的到个数多的顺序转移，我们不需要每次做卷积都重新FWT，只需要对于每一维直接记录整一维FWT后的结果，每次乘只需要点乘即可。

总的时间复杂度$O(2^nn^2)$

Code

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 23
#define M 1048576
#define LL long long
#define mo 1000000007
using namespace std;
LL f[M],g[M],a[N][N],ny;
int n,r,cnt[M],h[N][M],e[N][M];
void FWT(int *a,bool pd,int num)
{for(int m=2,half=1;m<=num;half=m,m<<=1)for(int j=0;j<num;j+=m)fo(i,j,j+half-1){int v=a[i+half];a[i+half]=(a[i]-v)%mo,a[i]=(a[i]+v)%mo;if(pd) a[i]=(LL)a[i]*ny%mo,a[i+half]=(LL)a[i+half]*ny%mo;}
}
int main()
{cin>>n;ny=(mo+1)/2;fo(i,0,n-1)fo(j,i+1,n-1) scanf("%lld",&a[i][j]);r=(1<<n)-1;int r1=r>>1,w=1<<(n-1);fo(i,0,r) {g[i]=1;fo(x,0,n-1) {if((1<<x)&i)fo(y,x+1,n-1) if((1<<y)&i) g[i]=g[i]*(a[x][y]+1)%mo; }if(i&w) f[i]=g[i];}f[0]=0;fo(i,1,r) cnt[i]=cnt[i-(i&(-i))]+1;fo(i,0,r1) {e[cnt[i]][i]=g[i];if(cnt[i]==0) h[0][i]=f[i^w];}fo(i,1,n-1) FWT(e[i],0,r1+1);fo(i,1,n-1){FWT(h[i-1],0,r1+1);fo(x,0,i-1){fo(j,0,r1) h[i][j]=(h[i][j]+(LL)h[x][j]*(LL)e[i-x][j])%mo;} FWT(h[i],1,r1+1);fo(j,0,r1) {if(cnt[j]!=i) h[i][j]=0;else h[i][j]=(g[j^w]-h[i][j]+mo)%mo;}}printf("%d\n",(h[n-1][r1]+mo)%mo);
}