about 4 years ago

prufer编码:http://baike.baidu.com/link?url=qyg7MKVSHg443qloXT46zqNijGxkd5voUpkE42UxkSVy286bsC2NHp5UAwveKJu2rWUQSUtO42Q9gWa__VkRZq
性质1:每一个prufer编码都与一棵无根树一一对应。
性质2:prufer编码长度=无根树节点个数-2
性质3:pruder编码里每一个数的出现次数+1 = 无根树中此结点的度数
性质4:很明显编码里不同的排列对应不同的无根树
sol:http://ydcydcy1.blog.163.com/blog/static/216089040201302303451866/

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#define Mod 1000000

#define maxn 100001

using namespace std;
int n,sum=0,r=0;int a[1001];
int result[maxn];
void mul(int *a,int b)
{
    int k=0,i;
    for (i=1;i<=a[0];i++)
      {
        k=a[i]*b+k;
        a[i]=k%Mod;
        k=k/Mod;
      }
    while (k) a[++a[0]]=k%Mod,k=k/Mod;
}
void div(int *a,int b)
{
    for (int k=0,i=a[0];i>=1;i--)
    {
        k=(a[i]+k*Mod);
        a[i]=k/b;
        k=k%b;
    }
    while (a[a[0]]==0) a[0]--;
}
int main()
{    int i,j;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if (a[i]==-1) r++;
        if (a[i]==0) {printf("0\n");return 0;};
        if (a[i]>0) a[i]--,sum+=a[i];
    }
    if (sum>n-2) {printf("0\n");return 0;};
    result[0]=result[1]=1;
    for (i=n-sum-1;i<=n-2;i++) mul(result,i);
    for (i=1;i<=n;i++) 
        for (j=a[i];j>=2;j--)div(result,j);
    for (i=1;i<=n-sum-2;i++) mul(result,r);
    printf("%d",result[result[0]]);
    for (i=result[0]-1;i>=1;i--)
      printf("%06d",result[i]);
}
← mobius反演 gcd相关 数学分块 【bzoj2434】【ac自动机】【fail树】【dfs序树状数组】阿狸的打字机 →
 
comments powered by Disqus