Dead Ends
\(n\le10\)，我还是第一次见到这么小的状压
我们设 \(f[S][s]\) 表示：将集合 \(S\) 内的点连成一棵树，且集合 \(s\) 里的节点是叶子节点的方案数。
则有
\[f[S\cup\{j\}][\{s\setminus i\}\cup\{j\}]+=f[S][s],i\in S,j\notin S,\exists(i,j)
\]
但是，一棵树可能会被不同的顺序构造出来。因此有 \(f[S][s]\) 应该除以 \(|s|\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=11;
int n,m,P,lim,res,x,y;
int f[1<<N][1<<N],g[N][N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>P;
lim=(1<<n);
for(int i=1;i<=m;i++){
cin>>x>>y;
x--;y--;g[x][y]=g[y][x]=1;
f[(1<<x)|(1<<y)][(1<<x)|(1<<y)]=2;
}
for(int p=1;p<lim;p++){
for(int q=p;q;q=(q-1)&p){
f[p][q]/=__builtin_popcount(q);
for(int i=0;i<n;i++){
if(!(p&(1<<i))) continue;
int t=q&((lim-1)^(1<<i));
for(int j=0;j<n;j++){
if(p&(1<<j)||!g[i][j]) continue;
f[p|(1<<j)][t|(1<<j)]+=f[p][q];
}
}
}
}
for(int i=0;i<lim;i++)if(__builtin_popcount(i)==P) res+=f[lim-1][i];
cout<<res;
return 0;
}