[HNOI2015]实验比较

[HNOI2015]实验比较

题目描述

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

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

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

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

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

代码：

#include<bits/stdc++.h>
#define ll long long
#define N 105

using 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<int>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<e[v].size();i++) {
        int to=e[v][i];
        if(ins[to]) {cout<<0;exit(0);}
        if(!vis[to]) chk_dfs(to);
    }
    ins[v]=0;
}

ll fac[N],ifac[N];
ll ksm(ll t,ll x) {
    ll ans=1;
    for(;x;x>>=1,t=t*t%mod)
        if(x&1) ans=ans*t%mod;
    return ans;
}

bool cmp(int a,int b) {return size[a]<size[b];}
ll inv2[N];

ll g[N][N][N];

void pre(int n) {
    //预处理g
    static ll f[N<<1][N][N][3];
    memset(f,0,sizeof(f));
    f[0][0][0][0]=1;
    for(int i=0;i<2*n;i++) {
        for(int j=0;j<=n;j++) {
            for(int k=0;k<=i;k++) {
                for(int q=0;q<3;q++) {
                    if(!f[i][j][k][q]) continue ;
                    if(j<n) {
                        (f[i+1][j+1][k+1][1]+=f[i][j][k][q])%=mod;
                        if(q==2) (f[i+1][j+1][k][0]+=f[i][j][k][q])%=mod;
                    }
                    if(i-j<n) {
                        (f[i+1][j][k+1][2]+=f[i][j][k][q])%=mod;
                        if(q==1) (f[i+1][j][k][0]+=f[i][j][k][q])%=mod;
                    }
                    (g[i-j][j][k]+=f[i][j][k][q])%=mod;
                }
            }
        }
    }
    for(int i=0;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            for(int k=0;k<=n;k++) {
                if(!g[i][j][k]) continue ;
                g[i][j][k]=g[i][j][k]*inv2[i+j-k]%mod;
            }
        }
    }
    for(int i=0;i<=n;i++) {
        for(int j=0;j<=n;j++) {
            for(int k=0;k<=n;k++) {
                if(!g[i][j][k]) continue ;
            }
        }
    }
}

ll dp[N][N];
ll tem[N];
void dfs(int v) {
    size[v]=0;
    dp[v][0]=1;
    for(int i=0;i<e[v].size();i++) {
        int to=e[v][i];
        dfs(to);
    }
    sort(e[v].begin(),e[v].end(),cmp);
    for(int i=0;i<e[v].size();i++) {
        int to=e[v][i];
        memset(tem,0,sizeof(tem));
        for(int j=0;j<=size[v];j++) {
            if(!dp[v][j]) continue ;
            for(int k=1;k<=size[to];k++) {
                for(int q=1;q<=j+k;q++) {
                    (tem[q]+=dp[v][j]*dp[to][k]%mod*g[j][k][q])%=mod;
                }
            }
        }
        size[v]+=size[to];
        memcpy(dp[v],tem,sizeof(tem));
    }
    size[v]++;
    for(int i=size[v];i>=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<<ans;
    return 0;
}