Go 解法, 执行用时: 748ms, 内存消耗: 10344K, 提交时间: 2022-12-17 11:37:38

package main

import "fmt"

const (
	M = int(1e5)
	mod = int(1e9) + 7
)

var g [M + 5][]int
var f [M + 5]int
var sz [M + 5]int
var fac [M + 5]int

func get_fac() {
	fac[0] = 1
	for i := 1; i <= M; i++ {
		fac[i] = fac[i - 1] * i % mod
	}
}

func quick(a int, b int) int {
	s := 1
	for b > 0 {
		if (b & 1) == 1 {
			s = s * a % mod
		}
		a = a * a % mod
		b >>= 1
	}
	return s % mod
}

func inv(n int) int {
	return quick(n, mod - 2)
}

func dfs(u int) {
	f[u], sz[u] = 1, 1
	for _, v := range g[u] {
		dfs(v)
		sz[u] += sz[v]
		f[u] = f[u] * f[v] % mod * inv(fac[sz[v]]) % mod
	}
	f[u] = f[u] * fac[sz[u] - 1] % mod
}

func main() {
	get_fac()
	var n int
	fmt.Scan(&n)
	sc := 1
	var c, fa int
	g[1] = make([]int, 0)
	for i := 1; i <= n; i++ {
		fmt.Scan(&c)
		g[1] = append(g[1], sc + 1)
		for j := 2; j <= c; j++ {
			fmt.Scan(&fa)
			g[sc + fa] = append(g[sc + fa], sc + j)
		}
		sc += c
	}
	dfs(1)
	fmt.Println(f[1])
}

C++(g++ 7.5.0) 解法, 执行用时: 43ms, 内存消耗: 3308K, 提交时间: 2022-08-20 15:56:32

#include<bits/stdc++.h>
using namespace std;using ll=long long;
#define endl '\n'
#define rep(i,l,r)for(ll(i)=(l);(i)<=(r);++(i))
const int MOD=1e9+7,N=1e5+10;ll f[N];int js;int qsm(int a,int b){ll res=1;while(b){if(b&1)res=res*a%MOD;a=(ll)a*a%MOD;b>>=1;}return res;}ll res=1;void Solve(){int n;cin>>n;vector<vector<int>>son(n+1);rep(i,2,n){int x;cin>>x;son[x].push_back(i);}vector<int>num(n+1);vector<ll>dp(n+1,1);function<void(int)>dfs=[&](int now){for(auto x:son[now]){dfs(x);num[now]+=num[x];dp[now]=dp[now]*dp[x]%MOD*qsm(f[num[x]],MOD-2)%MOD;}dp[now]=dp[now]*f[num[now]]%MOD;num[now]+=1;};dfs(1);res=res*dp[1]%MOD*qsm(f[num[1]],MOD-2)%MOD;rep(i,1,n)res=res*(++js)%MOD;return;}int main(){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);f[0]=1;rep(i,1,1e5)f[i]=f[i-1]*i%MOD;int t;cin>>t;while(t--)Solve();cout<<res;return 0;}

C++(clang++ 11.0.1) 解法, 执行用时: 52ms, 内存消耗: 3812K, 提交时间: 2023-02-03 17:20:34

#include<bits/stdc++.h>
using namespace std;
const int p=1e9+7;
const int N=1e5+5;
using ll=long long;

ll son[N],ans=1,sum;
vector<int>V[N];

ll qpow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}

void dfs(int x)
{
	son[x]++;
	for(auto u:V[x])
	{
		dfs(u);
		son[x]+=son[u];
	}
	ans=ans*qpow(son[x],p-2)%p;
}

int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int c;cin>>c;
		for(int i=1;i<=c;i++)
		{
			sum++;
			ans=ans*sum%p;
		}
		for(int i=1;i<=c;i++)
		{
			son[i]=0;
			V[i].clear();
		}
		for(int i=1;i<=c-1;i++)
		{
			int x;cin>>x;
			V[x].push_back(i+1);
		}
		dfs(1);	
	}
	cout<<ans;
	return 0;
}