[UVA11174] Stand in a line

Stand in a line

题意

给定$n-1​$组关系，节点$a​$不能站在节点$b​$的前面，使得$n​$站成一行，问有多少种站法。

题解

树形dp + 组合数学

1. 先建树，把没有父亲的节点都并入$0$节点，这样我们就有一颗完整的树了。
2. 寻找规律，假设$f[i]$为以$i$为根节点的方案数，那么当每增加一颗子树的时候，他的组合是相当于有一个有拓扑排序方案和另外一个拓扑排序方案相组合。

我们可以这样想像，假设拓扑排序是不存在的，这些点的排序忽略，那么点可以看做是同样颜色的点，那么$x_1,x_2$个数的点排列的排列数为$(x_1+x_2)! /(x_1! * x_2!)$。而这些点其实是不一样的，他们有自身的拓扑排序顺序，于是答案就是$f(x_1) f(x_2) (x_1+x_2)!/(x1! * x_2!)$。

3. 于是乎，我们先处理好每个节点的子节点(包含他自身)，可以用拓扑排序直接做，不用递归，当然也可以递归，于是就是相当于从子树开始处理，把所有子树的节点数的阶乘除掉就可以了。

简单写一下从递推到通向。$c_i$表示是$root$的子节点，$s(i)$表示$i$节点的子节点数。

$f(root) = f(c1)f(c2)…f(c_k)*((s(root)-1)!/s(c_1)!/s(c_2)!/…/s(c_k)!)$

$f(c_1)=f(x_1)f(x_2)…f(x_z)*((s(c_1)-1)!/s(x_1)!/s(x_2)!/…/s(x_z)!)$

$s(c_1)和s(c_1-1)$可以约掉。而且到叶子节点$f(x_1)$都变成$1$了$s(x_1)$也变成了0.

$f(root)=(s(root)-1)!/s(1)/s(2)/…/s(n)$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4 + 10;
const ll mod = 1e9 + 7;
int T,n,m,cnt;
struct node{
    int to,next;
}G[maxn<<1];
int head[maxn],vis[maxn],sz[maxn],q[maxn],pre[maxn];
ll fac[maxn],f[maxn];
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
void init(){
    cnt = 0;
    rep(i,0,n+1){
        vis[i] = 0;
        head[i] = -1;
        sz[i] = 0;
        pre[i] = 0;
        f[i] = 1;
    }
}
ll pow3(ll a,ll b){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a % mod;
        b>>=1;
    }
    return res;
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&T);
    fac[0] = 1;
    rep(i,1,maxn){
        fac[i] = fac[i-1]*i%mod;
    }
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,0,m){
            int u,v;scanf("%d%d",&v,&u);
            add(u,v);vis[v] = 1;
        }
        rep(i,1,n+1) if(!vis[i]) add(0,i);
        memset(vis,0,sizeof(vis));
        vis[0] = 1;
        int l=0,r=0; q[0] = 0;vis[0] = 1;
        while(l<=r){
            int u = q[l++];
            for(int i = head[u];~i;i=G[i].next){
                int v = G[i].to;
                if(vis[v]) continue;
                pre[v] = u;
                vis[u] = 1;
                q[++r] = v;
            }
        }
        per(i,1,n+1){
            sz[q[i]]++;
            sz[pre[q[i]]] += sz[q[i]];
        }
        sz[0]++;
        ll res = 0;
        ll cnt = fac[n];
        rep(i,1,n+1) cnt = cnt*pow3(sz[i],mod-2)%mod;
        printf("%lld\n",cnt);
    }
    return 0;
}

Reference:https://blog.csdn.net/xiao_k666/article/details/78609562