Niuke challenge 53:c. strange magic array

link ： Strange magic array (nowcoder.com)

The question ： Given $n$ Points and $m$ side , Find the number of independent subsets of all sets , namely ${\sum }_{S\subset T}[SbysinglestateSet]$, Then hash the number of independent sets of all sets to find the final answer , namely $ans={\sum }_{T\subset N}233^{{\sum }_{i\subset T}{2}^i}\ast {\sum }_{S\subset T}[SbysinglestateSet]$.

（ Define independent sets $S$ by $S$ All points in are isolated points , Two are not connected .）

Answer key ： According to the title, it is obviously necessary to enumerate $[0,2^n-1]$ All sets of , Then consider how to inherit the answer from the previously calculated set . It can be found that for a set $T$,$T$ It can be composed of two sets , The most convenient one is $T$ The lowest bit in binary system is a set with only one element , The remaining bits form another set （ It is not allowed to enumerate like ordinary pressure $n$ Positions make up $n$ Methods （ The set has no order ）, Just take it here once , Otherwise it will overlap ）.

Computing sets $y$ It can be used $\text{l}owbit$ The function takes the second power of the lowest order directly , Then subtract from the current set $y$ You can get $x$ aggregate , about $y$ And $x$ The combination of sets , Find out $y$ Corresponding element position $p[y]$, take $x$ Also the position of the element $mp$ value （ An element that has an edge with this element ） And , Then seek $x$ And the XOR of the result can be obtained $x$ Set does not match $y$ Conflicting point sets , The final answer is $f[i]=f[y]+f[x]+f[x\oplus (x\&mp[p[y]])]$

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn=(1<<26)+5;
const int mod=1e9+7;

int f[maxn],p[maxn],mp[30],n,m,x,y;
ll ans;

inline int lowbit(int x)
{
    
	return x&(-x);
}

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)p[1<<i]=i;
	for(int i=1;i<=m;i++)
	{
    
		cin>>x>>y;
		mp[x]|=1<<y;
		mp[y]|=1<<x;
	}
	for(int i=1;i<1<<n;i++)
	{
    
		int y=lowbit(i),x=i-y,z=x^(x&mp[p[y]]);
		if(i==y)f[i]=1;
		else f[i]=(1ll*f[y]+1ll*f[x]+1ll*f[z])%mod;
	}
	ll up=1;
	for(int i=0;i<1<<n;i++)
	{
    
		ans=(ans+up*(1ll*f[i]+1)%mod)%mod; up=up*233%mod;
	}
	cout<<ans<<endl;
	return 0;
}