给定nn个点，mm条边的无向图G=(V,E)G=(V,E)，求出它的完美匹配数量对106+3106+3取模的值。
一个完美匹配可以用一个排列ϕ:V→Vϕ:V→V来表示，满足(v,ϕ(v))∈E(v,ϕ(v))∈E和ϕ(ϕ(v))=vϕ(ϕ(v))=v。
输入
输入第一行，包含两个整数n,mn,m，表示图GG的点数和边数。
接下来mm行，第i+1i+1行包含两个正整数ui,viui,vi，描述第ii条无向边。ui,viui,vi为该边两个端点的标号。
保证图中没有自环或重边。
输出
输出一个整数，表示图GG的完美匹配数量对106+3106+3取模的值。
样例输入 样例输入14 41 31 42 32 4 样例输出 样例输出12 提示
样例2,3
样例解释1
排列(3,4,1,2)(3,4,1,2)和(4,3,2,1)(4,3,2,1)满足条件。
数据范围
来源
南外NOIP2017模拟
solution
这题问你匹配的方案数
如果n是奇数，那么就是0
偶数的话，考虑状压
令f[S]表示当前匹配的点状态为S
每次挑出两个0来匹配
用xfdsc状态，记忆化一下
效率O（可以过）
#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<algorithm>#include<cmath>#define maxn 33#define mod 1000003#define p 1000007using namespace std;int n,m,head[p],t1,t2,tot=1;int ma[maxn][maxn];struct node{ int v,nex,w;}e[p*3];void lj(int t1,int t2,int t3){ tot++;e[tot].v=t2;e[tot].w=t3;e[tot].nex=head[t1];head[t1]=tot;}int f(int S,int T){ for(int i=head[T];i;i=e[i].nex){ if(e[i].v==S)return e[i].w; } return -1;}int ask(int S){ if(!S)return 1; if(f(S,S%p+1)!=-1)return f(S,S%p+1); int fi=0,sum=0; for(;!(S&(1<<fi));fi++); for(int i=fi+1;i<=n;i++){ if((S&(1<<i-1))&&ma[fi+1][i])sum+=ask(S^(1<<fi)^(1<<i-1)); sum%=mod; } lj(S%p+1,S,sum); return sum;}int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d",&t1,&t2); ma[t1][t2]=ma[t2][t1]=1; } printf("%dn",ask((1<<n)-1)); return 0;}