一开始可以 3^n 子集DP，枚举一种状态的最后一个集合是什么来转移；
设 \( f[s] \) 表示 \( s \) 集合内的点都划分好了，\( g[s] = \sum\limits_{i \in s} w[i] \)
那么 \( f[s] = \sum\limits_{d \subseteq s} \frac{f[s-d] * g[d]}{g[s]} \)
注意判断一个集合是否合法，不仅要判断每个点的度数，还要判断整个集合是否连通；
这样就可以过 n <= 15 的点了，UOJ上有30分；
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=(<<)+,xxn=,xm=,mod=;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int n,m,p,f[xn],g[xn],w[xxn],g2[xn];
int hd[xxn],ct,to[xm],nxt[xm],bin[xxn];
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}
ll pw(ll a,int b){ll ret=; for(;b;b>>=,a=a*a%mod)if(b&)ret=ret*a%mod; return ret;}
bool vis[xxn];
int dfs(int x,int s)
{
vis[x]=; int ret=;
for(int i=hd[x],u;i;i=nxt[i])
if(!vis[u=to[i]]&&(s&bin[u-]))ret+=dfs(u,s);
return ret;
}
bool ck(int s)//
{
int cnt=;
for(int x=;x<=n;x++)
{
if(!(s&bin[x-]))continue;
int deg=; cnt++;
for(int i=hd[x];i;i=nxt[i])
{
if(s&bin[to[i]-])deg++;
}
if(deg&)return ;
}
for(int i=;i<=n;i++)vis[i]=;
for(int i=;i<=n;i++)
if(s&bin[i-])return dfs(i,s)!=cnt;
}
int main()
{
n=rd(); m=rd(); p=rd();
bin[]=; for(int i=;i<=n;i++)bin[i]=bin[i-]*;
for(int i=,x,y;i<=m;i++)x=rd(),y=rd(),add(x,y),add(y,x);
for(int i=;i<=n;i++)g[bin[i-]]=rd();
for(int s=;s<bin[n];s++)g[s]=upt(g[s&(-s)]+g[s^(s&(-s))]);
for(int s=;s<bin[n];s++)g[s]=pw(g[s],p),g2[s]=pw(g[s],mod-);
for(int s=;s<bin[n];s++)if(!ck(s))g[s]=;
int num=;
f[]=;
for(int s=;s<bin[n];s++)
{
for(int d=s;d;d=(s&(d-)))//d=s
f[s]=(f[s]+(ll)f[s^d]*g[d])%mod;
f[s]=(ll)f[s]*g2[s]%mod;
}
printf("%d\n",f[bin[n]-]);
return ;
}
3^n
关于FMT(其实和高维前缀和差不多)和子集卷积：https://www.cnblogs.com/Dance-Of-Faith/p/8818211.html
于是可以做子集卷积加速DP的过程。
代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=(<<)+,xxn=,xm=,mod=;
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return f?ret:-ret;
}
int n,m,p,f[xxn][xn],g[xxn][xn],w[xxn],g2[xn];
int hd[xxn],ct,to[xm],nxt[xm],bin[xxn],cnt[xn];
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}
ll pw(ll a,int b){ll ret=; for(;b;b>>=,a=a*a%mod)if(b&)ret=ret*a%mod; return ret;}
bool vis[xxn];
int dfs(int x,int s)
{
vis[x]=; int ret=;
for(int i=hd[x],u;i;i=nxt[i])
if(!vis[u=to[i]]&&(s&bin[u-]))ret+=dfs(u,s);
return ret;
}
bool ck(int s)//
{
int cnt=;
for(int x=;x<=n;x++)
{
if(!(s&bin[x-]))continue;
int deg=; cnt++;
for(int i=hd[x];i;i=nxt[i])
{
if(s&bin[to[i]-])deg++;
}
if(deg&)return ;
}
for(int i=;i<=n;i++)vis[i]=;
for(int i=;i<=n;i++)
if(s&bin[i-])return dfs(i,s)!=cnt;
}
int cal(int s){int ret=; while(s)ret+=(s&),s>>=; return ret;}
void fmt(int *a,int tp)
{
for(int d=;d<bin[n];d<<=)
for(int s=;s<bin[n];s++)
if(s&d)a[s]=upt(a[s]+a[s^d]*tp);
}
int main()
{
n=rd(); m=rd(); p=rd();
bin[]=; for(int i=;i<=n;i++)bin[i]=bin[i-]*;
for(int i=,x,y;i<=m;i++)x=rd(),y=rd(),add(x,y),add(y,x);
for(int s=;s<bin[n];s++)cnt[s]=cal(s);
for(int i=;i<=n;i++)g2[bin[i-]]=rd();
for(int s=;s<bin[n];s++)g2[s]=upt(g2[s&(-s)]+g2[s^(s&(-s))]);
for(int s=;s<bin[n];s++)g[cnt[s]][s]=pw(g2[s],p),g2[s]=pw(g[cnt[s]][s],mod-);
for(int s=;s<bin[n];s++)if(!ck(s))g[cnt[s]][s]=;
for(int i=;i<=n;i++)fmt(g[i],);
f[][]=; fmt(f[],);
for(int i=;i<=n;i++)
{
for(int j=;j<=i;j++)
for(int s=;s<bin[n];s++)
f[i][s]=(f[i][s]+(ll)f[j][s]*g[i-j][s])%mod;
fmt(f[i],-);
for(int s=;s<bin[n];s++)
if(cnt[s]==i)f[i][s]=(ll)f[i][s]*g2[s]%mod;
else f[i][s]=;
fmt(f[i],);
}
fmt(f[n],-);
printf("%d\n",f[n][bin[n]-]);
return ;
}