首页 > ACM题库 > HDU-杭电 > HDU 2974-Counting heaps[解题报告]HOJ
2014
02-24

HDU 2974-Counting heaps[解题报告]HOJ

Counting heaps

问题描述 :

We are given a rooted tree of n vertices. The vertices are to be labeled with numbers 1,2,…, n so that each label is unique and the heap condition holds, i.e. the label of any vertex is less than the label of its parent. How many such labellings exist? Since this number may be quite large, calculate only its
remainder modulo m.

输入:

The input contains several tree descriptions. The first line contains the number of input trees t (t <=250).

Each tree description begins with a line containing the size of the tree n (1 <= n <= 500000) and an integer m (2 <= m <= 10^9). n – 1 lines follow, i-th of which contains p(i + 1), the number of the parent of the i + 1-th vertex (1 <= p(i + 1) <= i). Vertex number 1 will be the root in each tree, so its parent will not be given. Total size of the input will not exceed 50MB.

输出:

The input contains several tree descriptions. The first line contains the number of input trees t (t <=250).

Each tree description begins with a line containing the size of the tree n (1 <= n <= 500000) and an integer m (2 <= m <= 10^9). n – 1 lines follow, i-th of which contains p(i + 1), the number of the parent of the i + 1-th vertex (1 <= p(i + 1) <= i). Vertex number 1 will be the root in each tree, so its parent will not be given. Total size of the input will not exceed 50MB.

样例输入:

4
3 1000000
1
1
4 1000000
1
1
1
5 1000000
1
2
3
4
5 1000000
1
1
3
3

样例输出:

2
6
1
8


Hint

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>

using namespace std;
const int MAX = 510000;
int pre[MAX], cnt[MAX];
int isleaf[MAX];
queue<int> q;
long long n, mod;

int prime[MAX], num_prime, cprime[MAX], isprime[MAX];

void init()
{
	scanf("%d%d", &n, &mod);
	pre[1] = -1;
	memset(isleaf, 0, sizeof(isleaf));
	for (int i = 2; i <= n; i++)
	{
		scanf("%d", &pre[i]);
		isleaf[pre[i]]++;
	}
	for (int i = 1; i <= n; i++)
		if (!isleaf[i])
			q.push(i);
}

void bfs()
{
	for (int i = 1; i <= n; i++)
		cnt[i] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		if (u == 1)
			continue;
		cnt[pre[u]] += cnt[u];
		isleaf[pre[u]]--;
		if (!isleaf[pre[u]])
			q.push(pre[u]);
	}
}

void prime_init()
{
	memset(isprime, 1, sizeof(isprime));
	int cnt = 0;
	isprime[0] = isprime[1] = -1;
	for (int i = 2; i < MAX; i++)
		if (isprime[i] != -1)
		{
			isprime[i] = cnt++;
			for (int j = 2; j * i < MAX; j++)
				isprime[i * j] = -1;
		}

	num_prime = 0;
	for (int i = 2; i <= MAX; i++)
		if (isprime[i] != -1)
			prime[num_prime++] = i;
}

void fac(int a, int v)
{
	for (int i = 0; a != 1; i++)
	{
		while (a % prime[i] == 0)
			cprime[i] += v, a /= prime[i];
		if (isprime[a] != -1)
			cprime[isprime[a]] += v, a = 1;
	}
}

long long pow(int a, int b)
{
	long long x = a, r = 1;
	while (b)
	{
		if (b & 1)
			r = (r * x) % mod;
		x = (x * x) % mod;
		b >>= 1;
	}
	return r;
}

long long solve()
{
	memset(cprime, 0, sizeof(cprime));
	for (int i = 2; i < n; i++)
		fac(i, 1);
	for (int i = 2; i <= n; i++)
		fac(cnt[i], -1);
	long long res = 1;
	for (int i = 0; i <= n && res != 0; i++)
		if (cprime[i])
			res = (res * pow(prime[i], cprime[i])) % mod;
	return res;
}

int main()
{
	prime_init();
	int t;
	scanf("%d", &t);
	while (t--)
	{
		init();
		bfs();
		cout << solve() << endl;
	}
	return 0;
}

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?