题意
给定一张 \(n\) 点 \(m\) 边的无向图，每个点都有权值 0，你现在要将一部分点的权值变成 1，使得边的两端的权值的按位或和为 1 的边的数量为偶数，求方案数。
\(n\le 40\)
分析
由于我是来学 FWT 的，所以不考虑线性代数。
不难发现题意可以转化成求边的两端权值都为 0 的边的数量为偶数的方案数。
\(n\le 40\) 一脸的折半啊，枚举前一半和后一半选哪些点，并让这些点权值设成 0。
下文称“左部边”为边的两端都为左部点的边，“右部边”同理，“中部边”则表示既不是左部边也不是右部边的边。
我们需要求 \(f_S\) 表示左部边两端都在 \(S\) 内的边数的奇偶性，\(g_S\) 同理表示右边，精细实现可以在 \(O(2^nn)\) 的复杂度内求出。
接着考虑所有中部边。本题最关键的一步，设 \(p_S\) 表示左边选 \(S\) 时右部点中与 \(S\) 的连边数为奇数的点集。那么假设右边选 \(T\)，则中部边的贡献即为 \(p_S\cap T\)。此时答案转化成 \(\sum_{S,T} [f_S\oplus g_T\oplus (\operatorname{popcount}(p_S\cap T)\bmod 2)\oplus (m\bmod 2)=0]\)。
考虑枚举 \(f_S,g_T\) 的值，则能计入答案的 \(\operatorname{popcount}(p_S\cap T)\) 的奇偶性固定。不妨设 \(a_R=\sum_{S,T}[p_S\cap T=R][f_S=x][g_T=y]\)，发现把第一项扔掉后 \(S,T\) 之间的计算是独立的，不妨再设 \(b_T=\sum_S[p_S=T][f_S=x],c_T=[g_T=y]\)，则 \(a_R=\sum_{S\cap T=R}b_Sc_T\)，这就是 AND-FWT 形式，时间复杂度 \(O(n2^n)\)。
代码：
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0);
#define OTIE cout.tie(0);
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define popc __builtin_popcountll
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline void ckmx(T1 &x,T2 y){x=x>y?x:y;}
template<typename T1,typename T2>inline void ckmn(T1 &x,T2 y){x=x<y?x:y;}
inline auto rd(){
int qwqx=0,qwqf=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')qwqf=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+ch-48;ch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char ch='\n'){
if(qwqx<0){qwqx=-qwqx;putchar('-');}
int qwqy=0;char qwqz[40];
while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}
while(qwqy--)putchar(qwqz[qwqy]);if(ch)putchar(ch);
}
bool Mbg;
const int maxn=45,maxm=1048576,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,n0,n1,m;
bool vis[maxn][maxn];
int cnt[maxm];
int p[maxm];
const int AND[2][2]={{1,1},{0,1}},IAND[2][2]={{1,-1},{0,1}};
inline void fwt(int n,int *arr,const int C[2][2]){
for(int len=1;len<n;len<<=1){
reprange(i,0,n-1,len<<1){
rep(j,i,i+len-1){
int x=arr[j],y=arr[j+len];
arr[j]=C[0][0]*x+C[0][1]*y,arr[j+len]=C[1][0]*x+C[1][1]*y;
}
}
}
}
inline void mul(int n,int *arr,int *brr){
fwt(n,arr,AND),fwt(n,brr,AND);
rep(i,0,n-1)arr[i]*=brr[i];
fwt(n,arr,IAND);
}
bool f[maxm],g[maxm];
int e[maxn];
int a[maxm],b[maxm];
inline void solve_the_problem(){
n=rd(),m=rd(),n0=n/2,n1=n-n0;
rep(i,1,m){
int x=rd(),y=rd();
vis[x][y]=vis[y][x]=1;
if(x<=n0&&y<=n0){
e[x]|=(1<<(y-1)),e[y]|=(1<<(x-1));
}
if(x>n0&&y>n0){
e[x]|=(1<<(y-n0-1)),e[y]|=(1<<(x-n0-1));
}
}
rep(i,n0+1,n){
mem(cnt,0);
rep(S,1,(1<<n0)-1){
int q=__builtin_ctz(S);
cnt[S]=cnt[S^(1<<q)]+vis[i][q+1];
if(cnt[S]&1)p[S]|=(1<<(i-n0-1));
}
}
rep(S,0,(1<<n0)-1){
int T=0;
rep(i,1,n0)if((S>>(i-1))&1){
f[S]^=popc(e[i]&T)&1;
T|=(1<<(i-1));
}
}
rep(S,0,(1<<n1)-1){
int T=0;
rep(i,n0+1,n)if((S>>(i-n0-1))&1){
g[S]^=popc(e[i]&T)&1;
T|=(1<<(i-n0-1));
}
}
int ans=0;
const int len=1<<n1;
rep(x,0,1)rep(y,0,1){
rep(i,0,len-1)a[i]=b[i]=0;
rep(S,0,(1<<n0)-1)a[p[S]]+=f[S]^x^1;
rep(S,0,len-1)b[S]=g[S]^y^1;
// rep(i,0,len-1)write(a[i],32);P__;
// rep(i,0,len-1)write(b[i],32);P__;
mul(len,a,b);
// rep(i,0,len-1)write(a[i],32);P__;
rep(S,0,len-1){
if((popc(S)&1)^x^y^(m&1))continue;
ans+=a[S];
}
}
write(ans);
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);
fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);
int _=1;
while(_--)solve_the_problem();
}
/*
*/