首先对于给出的等于条件，我们可以直接把点合并。对于合并后的图，我们发现要么是环，要么是树，环则直接无解，树我们可以用树形DP处理一下。
我们发现每个序列都被“<”分成了若干块，我们设f[i][j]为以i为根的树被分成j块的方案。每次我们合并两棵子树，假设A子树原有i快，B子树有j块，合并后有K快，我们先将A的序列放入，方案数C(k,i)，如果i+j>k那么表示j中有些块要以等于形式和A合并，方案数C(i,i+j-k)，所以对新答案贡献为f[A][i]*f[B][j]*C(k,i)*C(i,i+j-k)，这样转移即可
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll; vector<int> v[111]; int mo=1000000007; int c[111][111],f[111],g[111],next[111],y[111]; int F[111][111],size[111],du[111]; bool vis[111],pz; int n,i,tt,x,z,kn,m,ans,j; void Read() { char c; while(c=getchar(),c!='<'&&c!='='); if(c=='=')kn=1; else kn=0; } int find(int r) { if(f[r]==r)return r; else f[r]=find(f[r]); return f[r]; } void star(int i,int j) { tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j; } void dfs(int x) { int j,k; size[x]=1; vis[x]=true; j=g[x]; while(j!=0){ k=y[j]; if(!vis[k]){ dfs(k); size[x]+=size[k]; } j=next[j]; } } void dp(int x) { int j,k,mx[3],i,l,ni,nj,nk,ad; int h[111][3]; bool pf; pf=false; memset(mx,0,sizeof(mx)); memset(h,0,sizeof(h)); j=g[x]; while(j!=0){ k=y[j]; dp(k); j=next[j]; if(!pf){ pf=true; for(i=0;i<=size[k];i++)h[i][0]=F[k][i]; mx[0]=size[k]; } else{ for(i=0;i<=size[k];i++)h[i][1]=F[k][i]; mx[1]=size[k]; mx[2]=mx[0]+mx[1]; for(i=0;i<=mx[2];i++)h[i][2]=0; for(ni=0;ni<=mx[0];ni++)if(h[ni][0]) for(nj=0;nj<=mx[1];nj++)if(h[nj][1]) for(nk=min(ni,nj);nk<=ni+nj;nk++){ ad=(ll)c[nk][ni]*c[ni][ni+nj-nk]%mo; ad=(ll)ad*h[ni][0]%mo*h[nj][1]%mo; h[nk][2]=(h[nk][2]+ad)%mo; } for(i=0;i<=mx[2];i++)h[i][0]=h[i][2]; mx[0]=mx[2]; } } if(!g[x])F[x][1]=1; else{ for(ni=0;ni<=mx[0];ni++)F[x][ni+1]=h[ni][0]; } } int main() { scanf("%d%d",&n,&m); for(i=0;i<=100;i++){ c[i][0]=1; c[i][i]=1; } for(i=2;i<=100;i++) for(j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo; for(i=1;i<=n;i++)f[i]=i; for(i=1;i<=m;i++){ scanf("%d",&x); Read(); scanf("%d",&z); if(kn==0)v[x].push_back(z); else{ x=find(f[x]); z=find(f[z]); f[z]=x; } } for(i=1;i<=n;i++)f[i]=find(f[i]); for(i=1;i<=n;i++){ x=i; x=find(f[x]); for(j=0;j<v[i].size();j++){ z=find(f[v[i][j]]); star(x,z); du[z]++; } } pz=true; size[n+1]=1; for(i=1;i<=n;i++){ if(f[i]==i&&du[i]==0){ dfs(i); star(n+1,i); size[n+1]+=size[i]; } } for(i=1;i<=n;i++)if(f[i]==i&&!vis[i])pz=false; if(pz==false)printf("0 "); else{ dp(n+1); for(i=1;i<=size[n+1]+1;i++)ans=(ans+F[n+1][i])%mo; printf("%d ",ans); } }