首页 > 代码库 > UVA 1436 - Counting heaps(计数问题)
UVA 1436 - Counting heaps(计数问题)
UVA 1436 - Counting heaps
题目链接
题意:给定一个树的结构,放1-n数字进去,父亲结点值必须小于子节点,问情况有几种.
思路:f[u]表示以u为子树的情况,那么子树情况为f(v1), f(v2), f(v3)... f(vn).去组成子树相当于从中选s(v1), s(v2), s(v3) ... s(vn).根据组合数学,情况为f(v1)f(v2) ... f(vn) (s(u) - 1)! \ (s(v1)!s(v2)! ... * s(vn)!)化简后得到公式:
f(u) = (s(root) - 1)! / s(1)s(2)s(3)...s(n)
由于答案很大要模上m,但是m不是素数,不能直接求逆,只能把分子分母分别分解质因子去消,最后得到都是分子形式在去取模。
代码:
#include <stdio.h> #include <string.h> #include <queue> using namespace std; const int N = 500005; int t, n, cnt[N], prime[N], vis[N], pn = 0, f[N], ispri[N]; long long m; int bfs() {//用dfs必然RE queue<int> Q; for (int i = 1; i <= n; i++) if (!vis[i]) Q.push(i); while (!Q.empty()) { int now = Q.front(); Q.pop(); if (now == 0) break; cnt[f[now]] += cnt[now]; vis[f[now]]--; if (vis[f[now]] == 0) Q.push(f[now]); } } void solve(int num, int v) { for (int i = 0; i < pn && prime[i] <= num; i++) { while (num % prime[i] == 0) { cnt[prime[i]] += v; num /= prime[i]; } if (ispri[num]) {//不加此剪枝必然TLE cnt[num] += v; break; } } } long long pow_mod(long long x, int k) { long long ans = 1; while (k) { if (k&1) ans = ans * x % m; x = x * x % m; k >>= 1; } return ans; } int main() { for (int i = 2; i < N; i++) { if (vis[i]) continue; ispri[i] = 1; prime[pn++] = i; for (int j = i; j < N; j += i) vis[j] = 1; } scanf("%d", &t); while (t--) { scanf("%d%lld", &n, &m); for (int i = 1; i <= n; i++) cnt[i] = 1; f[1] = 0; memset(vis, 0, sizeof(vis)); for (int i = 2; i <= n; i++) { scanf("%d", &f[i]); vis[f[i]]++; } bfs(); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) vis[cnt[i]]++; memset(cnt, 0, sizeof(cnt)); for (int i = 2; i <= n; i++) { solve(i, 1); if (vis[i]) solve(i, -vis[i]); } long long ans = 1; for (int i = 0; i < pn; i++) { if (cnt[prime[i]] == 0) continue; ans = (ans * pow_mod((long long)prime[i], cnt[prime[i]])) % m; } printf("%lld\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。