「BZOJ1005」[HNOI2008] 明明的烦恼

2014年5月30日11,1266

Description

自从明明学了树的结构,就对奇怪的树产生了兴趣…… 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

Input

第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1

Output

一个整数,表示不同的满足要求的树的个数,无解输出0

Sample Input

3
1
-1
-1

Sample Output

HINT

两棵树分别为1-2-3;1-3-2

题解

该题运用到了树的prufer编码的性质：

(1)树的prufer编码的实现

不断删除树中度数为1的最小序号的点，并输出与其相连的节点的序号直至树中只有两个节点

(2)通过观察我们可以发现

任意一棵n节点的树都可唯一的用长度为n-2的prufer编码表示

度数为m的节点的序号在prufer编码中出现的次数为m-1

(3)怎样将prufer编码还原为一棵树？？

从prufer编码的最前端开始扫描节点，设该节点序号为 u ,寻找不在prufer编码的最小序号且没有被标记的节点 v ，连接 u,v,并标记v，将u从prufer编码中删除。扫描下一节点。

该题需要将树转化为prufer编码：

n为树的节点数，d[ ]为各节点的度数，m为无限制度数的节点数。

则

所以要求在n-2大小的数组中插入tot各序号，共有

种插法；

在tot各序号排列中，插第一个节点的方法有

种插法；

插第二个节点的方法有

种插法；

………

另外还有m各节点无度数限制，所以它们可任意排列在剩余的n-2-tot的空间中，排列方法总数为

；

根据乘法原理：

然后就要高精度了…..但高精度除法太麻烦了，显而易见的排列组合一定是整数，所以可以进行质因数分解，再做一下相加减。

关于n!质因数分解有两种方法，第一种暴力分解，这里着重讲第二种。

若p为质数，则n!可分解为一个数*

，其中

且

所以

——转自怡红公子

蒟蒻只敢写了个暴力分解

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define mod 1000000
#define ll long long 
using namespace std;
inline 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*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}
int n,m,tot,cnt;
int d[1005],num[1005],pri[1005];
int ans[1005],l=1;
inline bool jud(int x)
{
     for(int i=2;i<=sqrt(x);i++)
         if(x%i==0)return 0;
     return 1;
}
void getpri()
{
     for(int i=2;i<=1000;i++)
         if(jud(i))pri[++cnt]=i;
}
void solve(int a,int f)
{
	 for(int k=1;k<=a;k++)
	 {
	 	 int x=k;
         for(int i=1;i<=cnt;i++)
         {
             if(x<=1)break;
             while(x%pri[i]==0)
             {num[i]+=f;x/=pri[i];}
         }
	 }
}
void mul(int x)
{
	for(int i=1;i<=l;i++)
	    ans[i]*=x;
	for(int i=1;i<=l;i++)
	{
	    ans[i+1]+=ans[i]/mod;
	    ans[i]%=mod;
    }
    while(ans[l+1]>0)
	{l++;ans[l+1]+=ans[l]/mod;ans[l]%=mod;}
}
void print()
{
	for(int i=l;i>0;i--)
	    if(i==l)printf("%d",ans[i]);
		else printf("%06d",ans[i]);
}
int main()
{
     getpri();ans[1]=1;
     n=read();
     if(n==1)
     {
         int x=read();
         if(!x)printf("1");
         else printf("0");
         return 0;
     }
     for(int i=1;i<=n;i++)
     {
         d[i]=read();
         if(!d[i]){printf("0");return 0;}
         if(d[i]==-1)m++;
		 else {d[i]--;tot+=d[i];}
     }
     if(tot>n-2){printf("0");return 0;}
     solve(n-2,1);
     solve(n-2-tot,-1);
     for(int i=1;i<=n;i++)
         if(d[i])solve(d[i],-1);
     for(int i=1;i<=cnt;i++)
         while(num[i]--)
             mul(pri[i]);
     for(int i=1;i<=n-2-tot;i++)
         mul(m);
     print();
     return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#define mod 1000000

#define ll long long

using namespace std;

inline 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*=10;x+=ch-'0';ch=getchar();}

return x*f;

}

int n,m,tot,cnt;

int d[1005],num[1005],pri[1005];

int ans[1005],l=1;

inline bool jud(int x)

{

for(int i=2;i<=sqrt(x);i++)

if(x%i==0)return 0;

return 1;

}

void getpri()

{

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

if(jud(i))pri[++cnt]=i;

}

void solve(int a,int f)

{

for(int k=1;k<=a;k++)

{

int x=k;

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

{

if(x<=1)break;

while(x%pri[i]==0)

{num[i]+=f;x/=pri[i];}

}

void mul(int x)

{

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

ans[i]*=x;

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

{

ans[i+1]+=ans[i]/mod;

ans[i]%=mod;

}

while(ans[l+1]>0)

{l++;ans[l+1]+=ans[l]/mod;ans[l]%=mod;}

}

void print()

{

for(int i=l;i>0;i--)

if(i==l)printf("%d",ans[i]);

else printf("%06d",ans[i]);

}

int main()

{

getpri();ans[1]=1;

n=read();

if(n==1)

{

int x=read();

if(!x)printf("1");

else printf("0");

return 0;

}

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

{

d[i]=read();

if(!d[i]){printf("0");return 0;}

if(d[i]==-1)m++;

else {d[i]--;tot+=d[i];}

}

if(tot>n-2){printf("0");return 0;}

solve(n-2,1);

solve(n-2-tot,-1);

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

if(d[i])solve(d[i],-1);

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

while(num[i]--)

mul(pri[i]);

for(int i=1;i<=n-2-tot;i++)

mul(m);

print();

return 0;

}

« 「BZOJ1211」[HNOI2004] 树的计数「泉七培训 – 郑予凡」致命漏洞 »

Steaunk

题面挂掉啦

姬树流

黄学长，你内个特盘如果n==1 && x==-1不就错了？

cgh

许羿

恩……找到一组错误数据：
5
1
2
1
1
1
你的输出是0正确答案是3.

orz hzwer

黄学长，在n-2大小的数组中插入tot各序号不应该是C(tot,n-1)种插法吗。。是首或尾不能插吗。。

hzwer

n-2个格子挑tot个放序号

黑暗世界

我记得我当时暴力高精除单精T_T

hzwer.com _ Home | http://hzwer.com

「BZOJ1005」[HNOI2008] 明明的烦恼

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论