首页 > 代码库 > 【BZOJ 1005】无根树的Prufer数列

【BZOJ 1005】无根树的Prufer数列

2024-07-17 02:54:56   226人阅读

今天看了Prufer数列这个东西。

每一个Prufer数列和无根树是一一对应的。所以求出有多少符合要求的Prufer数列即可。

点i在Prufer数列中的出现次数为i的度数 - 1。

 

代码如下：【用分解质因数的方法，避免了高精除】

#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int N = 10000 + 5, Prime_N = 1450 + 5;int n, Prime[Prime_N], A[N], p[Prime_N], Ans[N], P = 0, Bg, l, K;bool isPrime[N];void Add(int num, int Flag){    for (int i = 1; i <= P; i++)    {        if (Prime[i] > num) break;        while (num % Prime[i] == 0)        {            p[i] += Flag;            num /= Prime[i];        }    }}void Cheng(int num){    for (int i = 1; i <= l; i++) Ans[i] *= num;    for (int i = 1; i <= l; i++)    {        Ans[i + 1] += Ans[i] / 10;        Ans[i] %= 10;    }    while (Ans[l + 1])    {        l++;        Ans[l + 1] += Ans[l] / 10;        Ans[l] %= 10;    }}int main(){    scanf("%d", &n);        for (int i = 1; i <= n; i++) scanf("%d", A + i);    for (int i = 1; i <= n; i++) isPrime[i] = true;    isPrime[1] = false;    for (int i = 2; i <= n; i++)    {        if (isPrime[i]) Prime[++P] = i;        for (int j = 1; j <= P && i * Prime[j] <= n; j++)            isPrime[i * Prime[j]] = false;    }    memset(p, 0, sizeof(p));    Bg = n - 2;    K = n;    for (int i = 1; i <= n; i++)    {        if (A[i] != -1)        {            K--;            for (int j = 1; j <= A[i] - 1; j++)            {                Add(Bg, 1);                Bg--;                Add(j, -1);            }        }    }    Ans[1] = 1;    l = 1;    for (int i = 1; i <= P; i++)        for (int j = 1; j <= p[i]; j++)            Cheng(Prime[i]);    for (int i = 1; i <= Bg; i++) Cheng(K);    for (int i = l; i >= 1; i--) printf("%d", Ans[i]);    printf("\n");    return 0;}

 


联系
我们