前两个个小时过了五题，后三个小时一题没过，三个人盯一份代码盯了2个小时愣是没看出来，心态爆炸。
题意是给你一朵花状无向图，两个人同时走，A走过的边染成蓝色，B走过的边染成红色，走过的边就不能再走，直到其中一个人不能走的时候停下来，问有多少种染色方案。
很显然，我们可以把这朵花拍成数列，那么就是三种情况。
1、两个人在某一朵花瓣上相遇然后停止。
2、两个人各走个的环，走完整张图。
3、两个人各走各的，最后剩一条边。
那么我们就维护前后缀dp值，枚举那个环相遇然后合并就好了。
于是呢，我们把23当成一种情况考虑了，根本没有考虑少走一条边的人会在那个环停下来，GG。
#include<bits/stdc++.h> using namespace std; #define rll register ll #define IL inline #define rep(i,h,t) for (rll i=h;i<=t;i++) #define dep(i,t,h) for (rll i=t;i>=h;i--) #define mid ((h+t)>>1) #define ll long long const ll mo=1e9+7; const ll N=10000; struct re{ ll a,b,c; }e[N*2]; ll head[N],l,c[N],cnt,n,m; ll f1[3000][5000],f2[3000][5000]; IL void arr(ll x,ll y) { e[++l].a=head[x]; e[l].b=y; head[x]=l; } void cl(ll x) { if (x%2==1) e[x].c=1,e[x+1].c=1; else e[x].c=1,e[x-1].c=1; } void dfs(ll x,ll y) { if (x==1) { c[++cnt]=y; return; } for(rll u=head[x];u;u=e[u].a) { ll v=e[u].b; if (!e[u].c) { cl(u); dfs(v,y+1); } } } int main() { ios::sync_with_stdio(false); cin>>n>>m; rep(i,1,m) { ll x,y; cin>>x>>y; arr(x,y); arr(y,x); } for (rll u=head[1];u;u=e[u].a) { ll v=e[u].b; if (e[u].c==0) { cl(u); dfs(v,1); } } ll sum=0; for(int i=1;i<=cnt;++i)sum+=c[i]; m=cnt; f1[0][2000]=1; rep(i,1,m) { dep(j,4000,c[i]) f1[i][j]=(f1[i-1][j]+f1[i-1][j-c[i]])%mo; rep(j,0,4000-c[i]) f1[i][j]=(f1[i][j]+f1[i-1][j+c[i]])%mo; } f2[m+1][2000]=1; dep(i,m,1) { dep(j,4000,c[i]) f2[i][j]=(f2[i+1][j]+f2[i+1][j-c[i]])%mo; rep(j,0,4000-c[i]) f2[i][j]=(f2[i][j]+f2[i+1][j+c[i]])%mo; } ll ans=0; rep(i,1,m) { rep(i1,0,4000) if (f1[i-1][i1]>0) rep(j1,max(0ll,4000-c[i]-i1),min(4000ll,4000+c[i]-i1)) if (f2[i+1][j1]>0) { ll now=1ll*f1[i-1][i1]*f2[i+1][j1]%mo; ll kk=abs(i1+j1-4000); if (c[i]-2>=kk) ans=(ans+now)%mo; } } ans=ans*2%mo; // for(int i=1;i<=cnt;++i)cout<<c[i]<<" "; if(sum%2==1){ memset(f1,0,sizeof(f1)); memset(f2,0,sizeof(f2)); f1[0][2000]=1; rep(i,1,m) { dep(j,4000,c[i]) f1[i][j]=(f1[i][j]+f1[i-1][j-c[i]])%mo; rep(j,0,4000-c[i]) f1[i][j]=(f1[i][j]+f1[i-1][j+c[i]])%mo; } f2[m+1][2000]=1; dep(i,m,1) { dep(j,4000,c[i]) f2[i][j]=(f2[i][j]+f2[i+1][j-c[i]])%mo; rep(j,0,4000-c[i]) f2[i][j]=(f2[i][j]+f2[i+1][j+c[i]])%mo; } for(int i=1;i<=m;++i){ for(int j=0;j<=4000;++j){ if(4000+c[i]-1-j>=0&&4000+c[i]-1-j<=4000) (ans+=f1[i-1][j]*f2[i+1][4000+c[i]-1-j]%mo*2)%=mo; if(4000-c[i]+1-j>=0&&4000-c[i]+1-j<=4000) (ans+=f1[i-1][j]*f2[i+1][4000-c[i]+1-j]%mo*2)%=mo; } } } else{ memset(f1,0,sizeof(f1)); f1[0][2000]=1; rep(i,1,m) { dep(j,4000,c[i]) f1[i][j]=f1[i-1][j-c[i]]%mo; rep(j,0,4000-c[i]) f1[i][j]=(f1[i][j]+f1[i-1][j+c[i]])%mo; } ans=(1ll*ans+f1[m][2000]+1ll*(f1[m][2001]+f1[m][1999])*2)%mo; } cout<<ans<<endl; return 0; }