树的计数（prufer序列或 purfer序列）

题解

首先我们要知道一条性质，prufer序列中的某个点出现次数为该点在树中度数-1

感性理解一下，其实按照prufer序列求法自己推一下就出来了

设题目里给的度为$d[]$

先将所有的d--

然后按照排列组合得出来

这是多重集排列数

首先从n-2中选择d[1]个数是$C_{n}^{d[1]}$然后再从剩余n-d[1]中选d[2] $C_{n-d[1]}^{d[2]}$依次类推

$C_{n-2}^{d[1]}\times C_{n-2-d[1]}^{d[2]}\times C_{n-2-d[1]-d[2]}^{d[3]}\times ……\times C_{n-2-d[1]-……-d[n-1]}^{d[n]}$

得到

$\frac{(n-2)!}{\sum\limits_{i=1}^{n}d[i]!}$

高精转移就完了

还是过不了？

一些特判：

首先该题会有无解的情况

然后当只有一个点时方案数为1

然后当出现度数为0的点时方案数要特殊处理

以下是本人丑陋的代码

#include<bits/stdc++.h>

#define ll long long

#define N 10

#define P 1

using namespace std;

ll n,m,d[20000],cnt=0;

bool flag[20000];

struct bignum

{

    ll n[200000],l;

    bignum(){l=1,memset(n,0,sizeof(n));}

    void clear(){while(l>1&&!n[l-1]) l--;}

    void print()

    {

        printf("%lld",n[l-1]);

        for(ll i=l-2;i>=0;i--)

        printf("%0*lld",P,n[i]);

        printf("\n");

    }

    bignum operator = (ll x)

    {

        l=0;

        while(x)

        {

            n[l++]=x%N;

            x/=N;

        }

        return *this;

    }

    bignum operator +(bignum x) const

    {

        bignum t=*this;

        if(x.l>t.l) t.l=x.l;

        for(ll i=0;i<t.l;i++)

        {

            t.n[i]+=x.n[i];

            if(t.n[i]>=N)

            {

                t.n[i+1]+=t.n[i]/N;

                t.n[i]%=N;

            }

        }

        return t;

    }

       bignum operator * (const ll& b)

      {

        bignum c;

           c.l=0;

        for(ll i=0,g=0;g||i<l;i++)

        {

            ll x;

            if(i<l)x=n[i]*b+g;

            else x=g;

            c.n[c.l++]=x%N;

            g=x/N;

        }

        return c;

    }

    bignum operator *(bignum x) const

    {

        bignum t=*this,tep;

        tep.l=t.l+x.l+1;

        for(ll i=0;i<t.l;i++)

            for(ll j=0;j<=x.l;j++)

            {

                tep.n[i+j]+=t.n[i]*x.n[j];

            }

        for(ll i=0;i<tep.l;i++)

        {

            tep.n[i+1]+=tep.n[i]/N;

            tep.n[i]%=N;

        }

        tep.clear();

        return tep;

    }

    bool operator <(bignum x) const

    {

        bignum t=*this,tep;

        if(t.l!=x.l)    return t.l<x.l;

        for(ll i=t.l-1;i>=0;i--)

        {

            if(t.n[i]!=x.n[i]) return t.n[i]<x.n[i];

        }

        return 0;

    }

    bool operator >(bignum x) const

    {

        bignum t=*this;

        if(t.l!=x.l) return t.l>x.l;

        for(ll i=t.l-1;i>=0;i--)

        {

            if(t.n[i]!=x.n[i]) return t.n[i]>x.n[i];

        }

        return 0;

    }

    bignum operator -(bignum x) const

    {

        bignum t=*this;

        if(t<x) printf("-"),swap(t,x);

        ll jie=0;

        for(ll i=0;i<t.l;i++)

        {

            t.n[i]-=x.n[i];

            while(t.n[i]<0)

            {

                t.n[i]+=N;

                jie++;

            }

            t.n[i+1]-=jie;

            jie=0;;

        }

        t.clear();

        return t;

    }

    bignum operator /(const ll &x)

    {

        bignum t=*this,r;

        ll tmp=0;

        r.l=t.l;

        for(ll i=t.l-1;i>=0;i--){

            tmp+=t.n[i];

            if(tmp>=x){

                r.n[i]=tmp/x;

                tmp%=x;

            }

            tmp*=N;

        }

        r.clear();

        return r;

    }

}ans;

bignum jie(ll x)

{

    bignum t;t=1;

    for(ll i=2;i<=x;i++){

        t=x*i;

    }

    return t;

}

int main()

{

    memset(flag,0,sizeof(flag));

    ll sum=0,you0=0;

    scanf("%lld",&n);

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

    {

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

        if(d[i])flag[i]=1,cnt++;

        else you0=1;

        d[i]--,sum+=d[i];

    }

    if(you0&&n==1){

        cout<<1<<endl;

        return 0;

    }

    if(sum!=n-2||you0)

    {

        cout<<0<<endl;

        return 0;

    }

    ans=1;

    for(ll i=2;i<=cnt-2;i++)

        ans=ans*i;

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

        if(flag[i])

        for(ll j=2;j<=d[i];j++)

                ans=ans/j;

    }

    ans.print();

}

巴特西

树的计数（prufer序列或 purfer序列）

题解

一些特判：

最新文章

热门文章

巴特西

树的计数（prufer序列 或 purfer序列）

题解

一些特判：

最新文章

热门文章

树的计数（prufer序列或 purfer序列）