「BZOJ1211」[HNOI2004] 树的计数

2014年5月30日5,2410

Description

一个有n个结点的树，设它的结点分别为v1, v2, …, vn，已知第i个结点vi的度数为di，问满足这样的条件的不同的树有多少棵。给定n，d1, d2, …, dn，编程需要输出满足d(vi)=di的树的个数。

Input

第一行是一个正整数n，表示树有n个结点。第二行有n个数，第i个数表示di，即树的第i个结点的度数。其中1<=n<=150，输入数据保证满足条件的树不超过10^17个。

Output

输出满足条件的树有多少棵。

Sample Input

4
2 1 2 1

Sample Output

题解

明明的烦恼简化版。。

过程要分解质因数，不然爆long long

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#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[155],num[155],pri[155];
ll s[25],ans=1;
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<=150;i++)
         if(jud(i))pri[++cnt]=i;
}
void solve(ll x,int f)
{
     for(int i=1;i<=cnt;i++)
     {
         if(x<=1)return;
         while(x%pri[i]==0)
         {num[i]+=f;x/=pri[i];}
     }
}
int main()
{
     s[1]=1;
     for(int i=2;i<=22;i++)
         s[i]=s[i-1]*i;
     getpri();
     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;}
         d[i]--;
         tot+=d[i];
     }
     if(tot!=n-2){printf("0");return 0;}
     solve(s[n-2],1);
     for(int i=1;i<=n;i++)
         solve(s[d[i]],-1);
     for(int i=1;i<=cnt;i++)
         while(num[i]--)
             ans*=pri[i];
     printf("%lld",ans);
     return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#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[155],num[155],pri[155];

ll s[25],ans=1;

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<=150;i++)

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

}

void solve(ll x,int f)

{

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

{

if(x<=1)return;

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

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

}

int main()

{

s[1]=1;

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

s[i]=s[i-1]*i;

getpri();

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;}

d[i]--;

tot+=d[i];

}

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

solve(s[n-2],1);

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

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

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

while(num[i]--)

ans*=pri[i];

printf("%lld",ans);

return 0;

}

« 「BZOJ3505」[CQOI2014] 数三角形「BZOJ1005」[HNOI2008] 明明的烦恼 »

分类目录

计数器 9786008
OI 课件=>

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