【題解】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 ;
}