题目还有一个条件是，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*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=;
const int mod=1e9+;
int jie[N],inv[N];
int n,m;
int qm(int x,int y){
int ret=;
while(y){
if(y&) ret=(ll)ret*x%mod;
x=(ll)x*x%mod;
y>>=;
}
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[*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=;
if(vis[x]) {
fl=false;return;
}
vis[x]=;
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=;j<=n;++j){
f[x][j]=;
}
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
for(reg j=;j<=n;++j){
f[x][j]=(ll)f[x][j]*f[y][j-]%mod;
}
}
for(reg j=;j<=n;++j){
f[x][j]=mo(f[x][j]+f[x][j-]);
// printf("f[%d][%d] : %d\n",x,j,f[x][j]);
}
}else{
for(reg i=;i<=n;++i) f[x][i]=i;
}
}
int main(){
rd(n);rd(m);
char ch[];
for(reg i=;i<=n;++i){
fa[i]=i;
}
fl=true;
for(reg i=;i<=m;++i){
rd(q[i].x);
scanf("%s",ch);
rd(q[i].y);
if(ch[]=='>') q[i].typ=;
else{
int k1=fin(q[i].x),k2=fin(q[i].y);
q[i].typ=;
fa[k1]=k2;
}
}
for(reg i=;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==){
if(mp[make_pair(k1,k2)]==){
add(k1,k2);
mp[make_pair(k1,k2)]=;
}
++du[k2];
}else if(q[i].typ==){
if(mp[make_pair(k2,k1)]==){
add(k2,k1);
mp[make_pair(k2,k1)]=;
}
++du[k1];
}
}
if(!fl){
// cout<<" no "<<endl;
puts("");return ;
}
for(reg i=;i<=n;++i){
if(fin(i)==i&&du[i]==){
add(,i);
}
}
// cout<<" fl "<<fl<<endl;
++n;//warning!! 0~n-1
dfs(,-); for(reg i=;i<=n-;++i){
if(!vis[fin(i)]) fl=false;
}
if(!fl){
// cout<<" no "<<endl;
puts("");return ;
}
jie[]=;
for(reg i=;i<=n;++i) jie[i]=(ll)jie[i-]*i%mod;
inv[n]=qm(jie[n],mod-);
for(reg i=n-;i>=;--i){
inv[i]=(ll)inv[i+]*(i+)%mod;
}
ll ans=;
for(reg i=;i<=n;++i){
for(reg j=;j<=i;++j){
if(j&) ans=mo(ans+mod-(ll)C(i,j)*f[][i-j]%mod);
else ans=mo(ans+(ll)C(i,j)*f[][i-j]%mod);
}
}
printf("%lld",ans);
return ;
} }
signed main(){
// freopen("4.in","r",stdin);
// freopen("4.out","w",stdout);
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/9 21:08:53
*/
总结：
建出树形结构
考虑链的拼凑情况。——O(n^3)
神仙二项式反演——O(n^2)
二项式反演这里，利用“前i个编号分配”其实是容易考虑的。因为不用“恰好”，所以不用枚举具体用哪几个
把 恰好->前i个 然后容斥（二项式反演本身就是容斥（也可以大力推式子））
我们实际上把“恰好”放在了外面，最后二项式反演时候再考虑。