题目还有一个条件是，x>y的y只会出现一次（每个数直接大于它的只有一个）
n<=5000
是 [HNOI2015]实验比较 的加强版
g(i,j,k)其实可以递推：g(i,j,k)=g(i-1,j,k-1)+g(i,j-1,k-1)+g(i-1,j-1,k-1)
代码：
判断无解的时候可能比较混乱
1.先保证不要连有向重边
2.如果不是树形图，就是有环，vis过了
#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=5005; const int mod=1e9+7; int jie[N],inv[N]; int n,m; int qm(int x,int y){ int ret=1; while(y){ if(y&1) ret=(ll)ret*x%mod; x=(ll)x*x%mod; y>>=1; } return ret; } int C(int n,int m){ return (ll)jie[n]*inv[m]%mod*inv[n-m]%mod; } struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; int du[N]; bool fl; void add(int x,int y){ // cout<<" x to y "<<x<<" "<<y<<endl; e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int fa[N]; struct con{ int x,y; int typ;//1:x<y 2:x=y 3:x>y }q[N]; map<pair<int,int>,int>mp,con; int fin(int x){ return fa[x]==x?x:fa[x]=fin(fa[x]); } int f[N][N]; int mo(int x){ return x>=mod?x-mod:x; //return x%mod; } bool vis[N]; void dfs(int x,int ff){ // cout<<" x ff "<<x<<" "<<ff<<" fl "<<fl<<endl; if(!fl) return; int son=0; if(vis[x]) { fl=false;return; } vis[x]=1; for(reg i=hd[x];i;i=e[i].nxt){ if(!fl) return; int y=e[i].to; ++son; dfs(y,x); } if(son){ for(reg j=1;j<=n;++j){ f[x][j]=1; } for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; for(reg j=1;j<=n;++j){ f[x][j]=(ll)f[x][j]*f[y][j-1]%mod; } } for(reg j=1;j<=n;++j){ f[x][j]=mo(f[x][j]+f[x][j-1]); // printf("f[%d][%d] : %d ",x,j,f[x][j]); } }else{ for(reg i=1;i<=n;++i) f[x][i]=i; } } int main(){ rd(n);rd(m); char ch[233]; for(reg i=0;i<=n;++i){ fa[i]=i; } fl=true; for(reg i=1;i<=m;++i){ rd(q[i].x); scanf("%s",ch); rd(q[i].y); if(ch[0]=='>') q[i].typ=3; else{ int k1=fin(q[i].x),k2=fin(q[i].y); q[i].typ=2; fa[k1]=k2; } } for(reg i=1;i<=m;++i){ if(!fl) break; // cout<<q[i].x<<" "<<q[i].y<<" "<<q[i].typ<<endl; int k1=fin(q[i].x),k2=fin(q[i].y); // if(!che(k1,k2,q[i].typ)) fl=false; // cmp[k1][k2]=q[i].typ; // cmp[k2][k1]=4-q[i].typ; if(q[i].typ==3){ if(mp[make_pair(k1,k2)]==0){ add(k1,k2); mp[make_pair(k1,k2)]=1; } ++du[k2]; }else if(q[i].typ==1){ if(mp[make_pair(k2,k1)]==0){ add(k2,k1); mp[make_pair(k2,k1)]=1; } ++du[k1]; } } if(!fl){ // cout<<" no "<<endl; puts("0");return 0; } for(reg i=1;i<=n;++i){ if(fin(i)==i&&du[i]==0){ add(0,i); } } // cout<<" fl "<<fl<<endl; ++n;//warning!! 0~n-1 dfs(0,-1); for(reg i=0;i<=n-1;++i){ if(!vis[fin(i)]) fl=false; } if(!fl){ // cout<<" no "<<endl; puts("0");return 0; } jie[0]=1; for(reg i=1;i<=n;++i) jie[i]=(ll)jie[i-1]*i%mod; inv[n]=qm(jie[n],mod-2); for(reg i=n-1;i>=0;--i){ inv[i]=(ll)inv[i+1]*(i+1)%mod; } ll ans=0; for(reg i=1;i<=n;++i){ for(reg j=0;j<=i;++j){ if(j&1) ans=mo(ans+mod-(ll)C(i,j)*f[0][i-j]%mod); else ans=mo(ans+(ll)C(i,j)*f[0][i-j]%mod); } } printf("%lld",ans); return 0; } } signed main(){ // freopen("4.in","r",stdin); // freopen("4.out","w",stdout); Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/2/9 21:08:53 */
总结：
建出树形结构
考虑链的拼凑情况。——O(n^3)
神仙二项式反演——O(n^2)
二项式反演这里，利用“前i个编号分配”其实是容易考虑的。因为不用“恰好”，所以不用枚举具体用哪几个
把 恰好->前i个 然后容斥（二项式反演本身就是容斥（也可以大力推式子））
我们实际上把“恰好”放在了外面，最后二项式反演时候再考虑。