【题解】UVA11174 递推+逆元+快速幂

题目链接

参考了大佬博客思路摘抄如下

首先我们可以把关系建成树，这样我们就有可能得到一个森林（或者是一课树），然后我们再虚拟出来一个点0连接所有森林的根节点，这样是为了保证是一棵树，然后题目就变成了给你一棵树，不改变关系，问这个树有多少种方式，这个还是排列组合问题，对于每一个根节点，有这样的性质

root[i] = f[1]f[2]..f[k] * (s[i]-1)!/s[1]!s[2]!..s[k]!

f[1]..f[k]表示的当前根节点连接的k个儿子为根节点的树的排列个数，s[i]表示的是以i为根节点的这棵树的所有节点个数，上面的式子可以理解成这样

f[1]f[2]..f[k] 所有儿子为根节点的排列个数

(s[i] - 1)! 表示的是以i为根的这棵树的所有节点数-1（不算跟所以-1）的排列方式

//s[1]!s[2]!..s[k]! 相当于全排列去掉重复部分，因为每一棵树已经f[]了，不能在了，不能再*那就可以理解成重复部分了，所以…，然后把每一个公式都化简，会发现分子剩1，分母剩s[i]了，（可以理解成分子的f[i]和分母的s[i]!约），这样最后剩下的是

((n+1）-1)/s1*s2*..sn;

最后的公式是

Ans = n!/(s1*s2*s3*s4…*sn) si是以i为根节点的子树的节点数

1e9+7是素数，模1e9+7的情况下除以x等于乘以x的逆元，快速幂

#include<cstdio>
#include<cstring>
const int mod=+;
const int N=+;
struct node{
    int to,next;
}e[N];
typedef long long ll;
ll sum[N],jc[N];
int head[N],tot;
int deg[N];
void db()
{
    ll now=;
    for(ll i=;i<=;i++)
    {
        now=now*i%mod;
        jc[i]=now;
    }
}
void addedge(int u,int v)
{
    e[++tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;
}
int dfs(int now)
{
    int s=;
    for(int k=head[now];k;k=e[k].next)
    s+=dfs(e[k].to);
    sum[now]=s;
    return s;
}
ll Pow(ll a,ll b)
{
    ll c=;
    while(b)
    {
        if(b&)c*=a;
        b>>=;
        a*=a;
        a=a%mod;
        c=c%mod;
    }
    return c;
}
int main()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif
    int n,m,a,b,t,i;
    db();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,,sizeof(head));
        memset(deg,,sizeof(deg));
        tot=;
        for(i=;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            addedge(b,a);
            deg[a]++;
        }
        for(i=;i<=n;i++)
        if(!deg[i])addedge(,i);
        memset(sum,,sizeof(sum));
        dfs();
        ll ans=jc[n];
        for(i=;i<=n;i++)
        ans=ans*Pow(sum[i],mod-)%mod;
        printf("%lld\n",ans);
    }
    return ;
}