P2290 题解

· · 题解

前置知识：

prufer 序列。

思路：

我们都知道，prufer 序列有以下性质：

  1. 可以与树互相转化。

  2. 对于 n 个点的树，转化成 prufer 序列后序列里有 n-2 个元素。

  3. 对于树上一个点，它在 prufer序列中的出现次数是它在树中的度数减去 1。

根据这些性质，我们可以转换问题：

构造一棵树转化为构造一个 prufer 序列。

那么就成了多重集的全排列问题：n-2 个元素，n 种元素，第 i 种元素有 deg_i-1 个（deg_i 为点 i 的度数）。

套公式就是：

{(n-2)!\over (deg_1-1)!\times (deg_2-1)!\times...\times (deg_n-1)!}

但是我们正常算可能会溢出，所以我们用一个模数（10^{17}+3 就可以）再用乘法逆元即可。因为总答案不会超过 10^{17}，所以不会影响正确性。

代码：

#include<bits/stdc++.h>
#define int __int128//因为1e17*1e17爆long long，所以用它
using namespace std;
const int cxk=155,mod=100000000000000003ll;
int fastpow(int x,int y)
{
    int lcq=1,pw=x%mod;
    for(int i=0;i<=62;i++,pw=pw*pw%mod)
        if(y>>i&1)
            lcq=lcq*pw%mod;
    return lcq;
}
int read()//输入
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void print(int x)//输出
{
    if(x<=9)
        cout<<(signed)(x);
    else
    {
        print(x/10);
        cout<<(signed)(x%10);
    }
}
int jc[cxk],n,deg[cxk],sum;
signed main()
{
    n=read();
    if(n==0)//特判一下
        cout<<1,exit(0);
    jc[0]=1;//0的阶乘等于1
    for(int i=1;i<=n;i++)
    {
        jc[i]=jc[i-1]*i%mod;//算阶乘
        deg[i]=read();
        sum+=deg[i];
        if((deg[i]<1&&n!=1)||deg[i]>=n)
            cout<<0,exit(0);
    }
    if(sum!=n*2-2)
        cout<<0,exit(0);
    int ans=jc[n-2];
    for(int i=1;i<=n;i++)
        ans=ans*fastpow(jc[deg[i]-1],mod-2)%mod;//乘逆元
    print(ans);
}