uva 1436 - Counting heaps(计数)

本文主要是介绍uva 1436 - Counting heaps(计数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 1436 - Counting heaps

题目大意：给出一个树的形状，现在为这棵树标号，保证根节点的标号值比子节点的标号值大，问有多少种标号树。

解题思路：和村名排队的思路是一只的uva11174,最后问题只和树德结构有直接关系，f(root)=(s(root)−1)!(s(1)∗s(2)∗⋯∗s(n)

但是给定的取模数不是质数，所以不能用逆元做，只能将分子分母分别拆分成质因子，然后对质因子进制约分。因为最后的答案一定是正整数，所以对于每个质因子，分子分解出的因子个数一定大于等于分母分解出的，最后约分肯定剩下的是分子，再用快速幂求解。

剪枝，因为分解质因子的次数非常多，所以需要对分解函数剪枝，当u是质数时，可以直接终止返回。

#include <cstdio>
#include <cstring>
#include <queue>using namespace std;const int N = 500005;
typedef long long ll;int P = 0, prime[N], ispri[N];
int n, f[N], vis[N], cnt[N];
ll mod;void getPrime (int N) {memset(ispri, 0, sizeof(ispri));for (int i = 2; i < N; i++) {if (ispri[i])continue;prime[P++] = i;for (int j = 2 * i; j < N; j += i)ispri[j] = 1;}
}void getNode () {memset(cnt, 0, sizeof(cnt));queue<int> que;for (int i = 1; i <= n; i++)if (vis[i] == 0)que.push(i);while (!que.empty()) {int u = que.front();que.pop();cnt[u]++;int v = f[u];cnt[v] += cnt[u];vis[v]--;if (vis[v] == 0)que.push(v);}
}void init () {memset(vis, 0, sizeof(vis));scanf("%d%lld", &n, &mod);f[1] = 0;for (int i = 2; i <= n; i++) {scanf("%d", &f[i]);vis[f[i]]++;}getNode();memset(vis, 0, sizeof(vis));for (int i = 1; i <= n; i++)vis[cnt[i]]++;
}ll power (ll x, ll m) {ll ans = 1;while (m) {if (m&1)ans = ans * x % mod;x = x * x % mod;m /= 2;}return ans;
}void cal (int u, int v) {for (int i = 0; i < P; i++) {int k = prime[i];while (u % k == 0) {cnt[k] += v;u /= k;}if (ispri[u] == 0) {cnt[u] += v;return;}}
}ll solve () {memset(cnt, 0, sizeof(cnt));for (int i = 2; i <= n; i++)cal(i, 1);for (int i = 2; i <= n; i++)if (vis[i])cal(i, -vis[i]);ll ans = 1;for (int i = 0; i < P; i++) {ll u = prime[i];if (cnt[u])ans = (ans * power(u, cnt[u])) % mod;}return ans;
}int main () {getPrime(N);int cas;scanf("%d", &cas);while (cas--) {init();printf("%lld\n", solve());}return 0;
}