题目：https://www.luogu.org/problemnew/show/P4547
https://www.lydsy.com/JudgeOnline/problem.php?id=5006
参考博客：https://www.cnblogs.com/yanshannan/p/9452802.html
注意同一个点连出去的两条边本来就不能一起选！
每次调用 map 会很慢！所以修改的时候新定义一个 &tmp，就能过了。
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #define il inline using namespace std; typedef long long ll; int rd() { int ret=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return f?ret:-ret; } int const xn=20,xm=(1<<15)+5,mod=1e9+7; int n,m,bin[16],ct; map<int,int>f[xm]; struct N{ int s,t,w; N(int s=0,int t=0,int w=0):s(s),t(t),w(w) {} }ed[1005]; il ll pw(ll a,int b){ll ret=1; for(;b;b>>=1,a=a*a%mod)if(b&1)ret=ret*a%mod; return ret;} il int upt(int x){while(x>=mod)x-=mod; while(x<0)x+=mod; return x;} il int dfs(int s,int t) { if(!s&&!t)return 1; if(f[s][t])return f[s][t]; int &tmp=f[s][t];// for(int i=1;i<=ct;i++) { if((ed[i].s<<1)<=s||(ed[i].s|s)!=s||(ed[i].t|t)!=t)continue;//t tmp=(tmp+(ll)dfs(s^ed[i].s,t^ed[i].t)*ed[i].w)%mod; } return tmp=upt(tmp);//- } int main() { n=rd(); m=rd(); bin[0]=1; for(int i=1;i<=15;i++)bin[i]=bin[i-1]*2; int inv2=pw(2,mod-2),inv4=pw(4,mod-2); for(int i=1,tp,a,b,c,d;i<=m;i++) { tp=rd(); a=rd(); b=rd(); ed[++ct]=N(bin[a-1],bin[b-1],inv2); if(!tp)continue; c=rd(); d=rd(); ed[++ct]=N(bin[c-1],bin[d-1],inv2); if(a==c||b==d)continue;//! if(tp==1)ed[++ct]=N(bin[a-1]|bin[c-1],bin[b-1]|bin[d-1],inv4); if(tp==2)ed[++ct]=N(bin[a-1]|bin[c-1],bin[b-1]|bin[d-1],-inv4); } printf("%lld ",(ll)dfs(bin[n]-1,bin[n]-1)*bin[n]%mod); return 0; }