BZOJ1211: [HNOI2004]树的计数

1211: [HNOI2004]树的计数

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1245 Solved: 383
[Submit][Status]

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

HINT

Source

组合数学

题解：

prufer序列裸题吧。。。

一直交上去0ms WA，实在受不鸟了交了lyd的代码。。。

代码：

mine

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 50000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int a[maxn],n,tot;

 bool v[maxn];

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     int sum=;

     for1(i,n)

      {

          int x=read()-;sum+=x;

          if(x<||x>=n){printf("");return ;};

          for1(j,x)a[++tot]=j;

      }

      if(n==&&sum==-){printf("");return ;}

      if(n==&&sum==){printf("");return ;}

     if(sum!=n-){printf("");return ;}

     sort(a+,a+tot+);

     ll ans=;

     for1(i,n-)

     {

       ans*=i;

       for1(j,tot)

         if(!v[j]&&ans%a[j]==)ans/=a[j],v[j]=;

     }

     printf("%lld\n",ans);

     return ;

 }

lyd

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int n,m,c[],i,j,sum;

 long long ans;

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output2.txt","w",stdout);

     cin>>n;

     if(n==) {cin>>m; if(m) cout<<<<endl; else cout<<<<endl; return ;}

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

     {

         scanf("%d",&m);

         if(m<||m>n) {cout<<<<endl; return ;}

         sum+=m-;

         for(j=;j<m;j++) c[j]++;

     }

     m=n-;

     if(sum!=m) {cout<<<<endl; return ;}

     ans=;

     for(i=;i<=m;i++)

     {

         ans*=i;

         for(j=;j<n;j++)

             while(c[j]&&ans%j==) c[j]--,ans/=j;

     }

     cout<<ans<<endl;

     return ;

 }

秒客网