【BZOJ 1211】 [HNOI2004]树的计数

在这里输入题意

【题解】

prufer数列的应用
http://www.cnblogs.com/AWCXV/p/7626625.html
这一题没有节点的度数不定。
因此。
所有节点的度数-1的和结果一定要是n-2.
否则就无解。

然后把tot代成n-2就好了。

做法就一样了。

(大体思路就是,从n-2个空格里面选出d[i]个空格放节点i,从n-2-d[i]个空格里面选出d[i+1]个空格放节点i+1

(化简一下就成为上文中的式子了。

(d[i]0的时候在n1的时候是有解的

(可以不用高精度了这题

(结论,n!质因数分解后每个质因数p的指数为∑n/i 其中i为i,i^2,i3...i^x 其中i^x<=n

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 150;

int n,d[N+10],cnt[N+10];

bool is[N+10];

bool ok(int n){

    int len = sqrt(n);

    for (int i = 2;i <= len;i++)

        if (n%i==0)

            return false;

    return true;

}

void go(int n,int delta){

    for (int i = 1;i <= n;i++){

        if (is[i]){

            int sum = 0;

            for (int j = i;j <= n;j*=i) sum+=n/j;

            cnt[i]+=sum*delta;

        }

    }

}

int main(){

    scanf("%d",&n);

    int tot = 0;

    for (int i = 1;i <= n;i++){

        scanf("%d",&d[i]);

        if (d[i]==0 && n!=1) return puts("0"),0;

        d[i]--;

        tot+=d[i];

    }

    if (tot!=n-2) return puts("0"),0;

    for (int i = 2;i <= n;i++)

        if (ok(i)) is[i] = true;

    go(n-2,1);

    for (int i = 1;i <= n;i++) go(d[i],-1);

    long long temp = 1;

    for (int i = 1;i <= n;i++)

        for (int j = 1;j <= cnt[i];j++)

            temp = temp*i;

    printf("%lld\n",temp);

    return 0;

}

巴特西

【BZOJ 1211】 [HNOI2004]树的计数

最新文章

热门文章