[HNOI2015]实验比较

题目首先给出了一个基环外向树，于是我们先缩环。一个环必须全部由\(=\)连接，否则答案为\(0\)。

缩了环过后就是一棵树了。

乍一看以为是经典的有序表合并问题，直接用组合数学搞定。可是题目中一个合法的序列可以存在\(=\)。这样我们\(DP\)就是了。

设\(g_{i,j,k}\)表示一个长度为\(i\)的有序表和一个长度为\(j\)的有序表，合并过后有\(k-1\)个\(<\)连接的方案数。

预处理出\(g\)过后就可以转移了。

代码：

#include
    
     #define ll long long#define N 105using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=1e9+7;int n,m;int fr[N],to[N],p[N];ll c[N][N];int f[N];int r[N];vector
     
      e[N];int Getf(int v) {return v==f[v]?v:f[v]=Getf(f[v]);}int size[N];bool vis[N],ins[N];void chk_dfs(int v) {    vis[v]=ins[v]=1;    for(int i=0;i
      
       >=1,t=t*t%mod)        if(x&1) ans=ans*t%mod;    return ans;}bool cmp(int a,int b) {return size[a]
       
        =1;i--) dp[v][i]=dp[v][i-1];    dp[v][0]=0;}int main() {    n=Get(),m=Get();    inv2[0]=1;    inv2[1]=mod+1>>1;    for(int i=1;i<=n;i++) inv2[i]=inv2[i-1]*(mod+1>>1)%mod;    pre(n);    for(int i=0;i<=n;i++) fac[i]=fac[i-1]*i%mod;    ifac[n]=ksm(fac[n],mod-2);    for(int i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;    for(int i=1;i<=n;i++) f[i]=i;    for(int i=0;i<=n;i++)        for(int j=0;j<=i;j++)            c[i][j]=(!j||i==j)?1:(c[i-1][j-1]+c[i-1][j])%mod;    int a,b;    char op;    for(int i=1;i<=m;i++) {        a=Get();        while(op=getchar(),op!='<'&&op!='=');        b=Get();        fr[i]=a,to[i]=b;        p[i]=op=='<';        if(!p[i]) f[Getf(a)]=Getf(b);    }    for(int i=1;i<=m;i++) {        if(p[i]) {            if(Getf(fr[i])==Getf(to[i])) {cout<<0;return 0;}            e[Getf(fr[i])].push_back(Getf(to[i]));            r[Getf(to[i])]++;        }    }        for(int i=1;i<=n;i++) if(Getf(i)==i&&!vis[i]) chk_dfs(i);    for(int i=1;i<=n;i++) {        if(Getf(i)==i&&!r[i]) e[0].push_back(i);    }    dfs(0);    ll ans=0;    for(int i=1;i<=n+1;i++) (ans+=dp[0][i])%=mod;    cout<