Niuke challenge 53c

C- Strange magic array _ Cattle challenge 53 (nowcoder.com)

The author's solution is very simple , direct dp（S） Express S How many independent set subsets are there in the set , Then investigate S Any element in i The situation of , From the previous state , Complexity （2^n）
But in fact, this problem can be optimized to (n * 2^(n/2)).
First , According to the statement in the title, finding the number of independent subsets in each set one by one can not find a faster algorithm , Because enumerating each set at this point is about to (2^n), The complexity will not be lower than this lower bound . therefore , Consider simplifying the formula of the final answer ：

    

Just exchange the enumeration order first , Open the next item

So now the problem is for each independent set , A formula to calculate its contribution to the final answer , Think about it first dp

For convenience dp, At this time, we can put i A weight val(i) Write it down as

And then when you transfer , Enumerate to collection S, First judge this S Is it feasible , If possible , about dp(S), You can enumerate any element i,dp(S) = dp(S - {i}) * val[i], The final statistical answer is for each dp（S） Multiply

Then add the answer .

And then I found this dp It can be optimized by half enumeration

Because consider a set that is an independent set S, We deal with S The set of all adjacent points in the set cant, that N-S A set in T Can be combined S Is still an independent set , If and only if T Is an independent set and T hand over cant For an empty set .

According to the dp The transfer formula of ,dp[S * T] = dp[S] * dp[T], Use techniques like prefixes and optimizations , We can start with dp Process the set of the first half points , Find out dp value , Then sum the prefixes of the set （ That is, the value of each position plus all its subset position values ）, Write it down as sum.

then , Like the second half of the first time dp value , At the same time, the contribution of before and after consolidation is counted . Suppose the current enumeration goes to S, Its adjacency point is cant_S, You can get this S Merge with the previous half of the set to produce a contribution of dp[S] * sum[ The first half of the collection - cant_S]

The bottleneck of complexity lies in the set prefix and that step , use fwt The complexity of the positive transformation of the combined convolution is O(n * 2^(n/2))

#include<bits/stdc++.h>
#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;
}