CF53E. Dead Ends

E. Dead Ends

---

这种状态压缩题目见得比较少。考前来一道。

---

容易观察到，这道题(n)过于小，这让我们联想到——状态压缩。

不妨定义(dp(S))代表生成树点集为(S)的方案数。那么，容易观察到，这个状态难以转移。

具体来说，当我们枚举(S)的子集时，我们不知道应该怎么做才能避免不重复地计算。

---

那么，怎么办？——给状态增加维度。

做过寿司晚宴的同学都知道（我就不知道sigh），集合定义可以是两维的。我们不妨定义这样一个状态：(dp(S_1,S_2)) 代表生成树点集为 (S_1)，叶子结点集合为(S_2)的方案数。

这样一来，我们便能够列出状态转移方程了。

考虑该点集下生成树的所有可能形态。容易观察，这些方案中对于任意一个叶子结点，要么其父节点只有它这一个子节点，要么“多子”。由此，我们可以利用这一点进行计数。

枚举任意一个叶子结点(i)，该点集 (S_1) 下所有与它联通的点均可以成为其父节点。因此，我们在集合(S_1setminus S_2)中枚举节点(j)，当且仅当 (i) 和 (j) 联通时，有贡献 (dp(S_1setminus{i},S_2setminus{i})+dp(S_1setminus{i},S_2setminus{i}cup{j})) ，前者对应父节点“多子”，后者对应只有一个儿子。

即——

[dp(S_1,S_2)=sum_{forall iin S_2且jin S_1setminus S_2} dp(S_1setminus{i},S_2setminus{i})+dp(S_1setminus{i},S_2setminus{i}cup{j}) ]

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define RE register
#define CLR(x, y) memset(x,y,sizeof x)
#define FOR(i, x, y) for(RE int i=x;i<=y;++i)
#define ROF(i, x, y) for(RE int i=x;i>=y;--i)
#define lowbit(x) (x&(-x))
using namespace std;

const int MAXN = 11, INF = 1 << 30, SIZE = 1 << 11;

typedef long long LL;

bool mp[MAXN][MAXN] = {};
int n, m, k, t;
LL dp[SIZE][SIZE] = {};
int ttt[SIZE] = {}, siz[SIZE] = {};

int main()
{
//	freopen("T.in", "r", stdin);
	scanf("%d %d %d", &n, &m, &k);
	t = 1 << n, -- t;
	FOR(i, 1, m)
	{
		int u, v;
		scanf("%d %d", &u, &v);
		mp[u][v] = mp[v][u] = true;
		dp[(1 << u - 1) | (1 << v - 1)][(1 << u - 1) | (1 << v - 1)] = 1;
	}
	
	//initializing : 
	FOR(i, 1, t) siz[i] = siz[i & ~lowbit(i)] + 1;
	FOR(i, 1, n) ttt[1 << i - 1] = i;
	FOR(i, 1, t) ttt[i] = ttt[lowbit(i)];
	
	FOR(s0, 1, t)
	{
		if(siz[s0] <= 2) continue;
		for(RE int s1 = s0, s2; s1; s1 = (s1 - 1) & s0, s2 = s0 & ~s1)// 枚举子集 
		{
			if(siz[s1] == siz[s0] || siz[s1] < 2) continue;
			for(int S = s2, j = ttt[S]; S; j = ttt[S &= ~ (1 << j - 1)])
				dp[s0][s1] += mp[j][ttt[s1]] * (dp[s0 & ~(1 << ttt[s1] - 1)][(s1 & ~(1 << ttt[s1] - 1)) | (1 << j - 1)] + dp[s0 & ~(1 << ttt[s1] - 1)][s1 & ~(1 << ttt[s1] - 1)]);
		}
	}
	LL res = 0;
	FOR(i, 1, t) if(siz[i] == k) res += dp[t][i];
	printf("%lld
", res);
	return 0;
}