C-奇奇怪怪的魔法阵 折半枚举做法

出题人的题解很简洁，直接dp（S）表示S集合内有多少个独立集子集，然后考察S中随便一个元素i的情况，由之前状态转移过来，复杂度（2^n）

但是事实上这道题可以通过折半枚举的方法优化到(n * 2^(n/2))。

首先，按照题目中的说法一个一个求每个集合T内独立子集个数肯定不能找到更快的算法，因为此时枚举每个集合就要(2^n)，复杂度不会低于这个下界。因此，考虑将最终答案的式子化简一下：

就是先交换一下枚举顺序，再把后面一项打开

那么现在问题就是对于每个独立集，计算它对最终答案贡献的一个式子，同样考虑dp

为了方便dp，此时我们可以把点i的权值val(i)记为

然后转移时，枚举到集合S，先判断这个S是否可行，如果可行，对于dp(S),就可以随便枚举一个元素i，令dp(S) = dp(S - {i}) * val[i]，最终统计答案时每个dp（S）乘上一个 bas = 后加入答案即可

之后发现这个dp是可以用折半枚举优化的

因为考虑一个是独立集的集合S，我们处理出#S集合内所有点#的邻接点点集cant，那么补集N-S中一个集合T能并上S仍然是独立集，当且仅当T是独立集且T交cant为空集。

而根据dp的转移式子，dp[S * T] = dp[S] * dp[T]，运用类似前缀和优化的技巧，我们就可以先dp处理前一半点的集合，求出dp值并把它的贡献加入答案中，然后对这一半的dp数组求集合前缀和（即每个位置的值加上所有它的子集位置值），记入sum数组。

然后,再类似第一遍求后一半dp值，dp同时统计与之前一半合并的贡献。假设当前枚举到S， 它的邻接点为cant_S,则可以得到这个S与之前一半的集合合并会产生的贡献为dp[S] * sum[{前一半集合} - cant_S]

折半枚举优化后，复杂度瓶颈在集合前缀和那一步，用fwt集合并卷积的正变换，复杂度为O(n * 2^(n/2))

#define pii pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define ll long long
#define trav(v,x) for(auto v:x)
#define all(x) ((x).begin(), (x).end())
#define VI vector<int>
#define VLL vector<ll>
using namespace std;
const int N = 26;
const int inf = 1e9;
const int mod = 1e9 + 7;

int n, m;
int a[N];

int hav[N], val[N], dp[1 << 14], sum[1 << 14];

int qpow(int x, int y)
{
	int res = 1;
	while(y)
	{
		if(y & 1)
			res = 1LL * res * x % mod;
		x = 1LL * x * x % mod;
		y >>= 1;
	}
	return res;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		hav[x] |= (1 << y);
		hav[y] |= (1 << x);
	}
	int bas = 1;
	for(int i = 0; i < n; i++)
		bas = 1LL * bas * (qpow(233, 1 << i) + 1) % mod;
	for(int i = 0; i < n; i++)
	{
		val[i] = qpow(233, 1 << i);
		val[i] = 1LL * val[i] * qpow(qpow(233, 1 << i) + 1, mod - 2) % mod;
	}
	int mid = n / 2;
	int ans = 0;
	int lim = 1 << mid;
	for(int S = 0; S < lim; S++)
	{
		if(S == 0)
		{
			dp[S] = bas;
			ans = (ans + dp[S]) % mod;
			continue;
		}
		int cant = 0;
		for(int i = 0; i < mid; i++)
		{
			if(S & (1 << i))
				cant |= hav[i];
		}
		if(cant & S)
			continue;
		int las = S & (-S), ps = __builtin_ffs(S) - 1;
		dp[S] = 1LL * dp[S - las] * val[ps] % mod;
		ans = (ans + dp[S]) % mod;
	}
	for(int l = 2, md = 1; l <= lim; l <<= 1, md <<= 1)
       for(int i = 0; i < lim; i += l)
           for(int j = 0; j < md; j++)
               dp[i + j + md] = (dp[i + j + md] + dp[i + j]) % mod;
    memcpy(sum, dp, sizeof dp);
    memset(dp, 0, sizeof dp);
    lim = (1 << (n - mid));
    dp[0] = 1;
    for(int S = 1; S < lim; S++)
	{
		int cant = 0, cantl, cantr;
		for(int i = 0; i < (n - mid); i++)
		{
			if(S & (1 << i))
				cant |= hav[i + mid];
		}
		cantl = cant & ((1 << mid) - 1);
		cantr = cant - cantl;
		cantr >>= mid;
		if(cantr & S)
			continue;
		int las = S & (-S), ps = __builtin_ffs(S) - 1;
		dp[S] = 1LL * dp[S - las] * val[ps + mid] % mod;
		ans = (ans + 1LL * dp[S] * sum[(1 << mid) - 1 - cantl]) % mod;
	}
	cout << ans << '\n';
	return 0;
}