1005: [HNOI2008]明明的煩惱
Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 1263 Solved: 498
[Submit][Status][Discuss]
Description
自從明明學了樹的結構,就對奇怪的樹產生了興趣...... 給出標號為1到N的點,以及某些點最終的度數,允許在任意兩點間連線,可產生多少棵度數滿足要求的樹?
Input
第一行為N(0 < N < = 1000),接下來N行,第i+1行給出第i個節點的度數Di,如果對度數不要求,則輸入-1
Output
一個整數,表示不同的滿足要求的樹的個數,無解輸出0
Sample Input
3
1
-1
-1
Sample Output
2
HINT
兩棵樹分別為1-2-3;1-3-2
PS:總之就是每一個樹都與一個prufer編碼一一對應，然後prufer編碼裡的數出現的個數正好是樹的這個點的度數減1。
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define ForD(i,n) for(int i=n;i>=1;i--)
#define MAXN (1000+10)
#define MAXLen (100000+10)
#define F (10000)
int n,degree[MAXN],T=0,blank_pos;
struct mul_arr
{
int a[MAXN];
int& operator[](int i){return a[i];}
mul_arr(){memset(a,0,sizeof(a));}
mul_arr(int m,int k) //pow(m,k)
{
memset(a,0,sizeof(a));
for(int i=2;i*i<=m;i++)
while (!(m%i))
{
a[i]+=k;m/=i;
}
if (m>1) a[m]+=k;
}
friend mul_arr operator-(mul_arr a,mul_arr b){For(i,n) a[i]-=b[i]; return a;}
friend mul_arr operator+(mul_arr a,mul_arr b){For(i,n) a[i]+=b[i]; return a;}
void print(){For(i,n) cout<<a[i]<<' ';cout<<endl;}
}_ans,jc;
struct Highn
{
int a[MAXN],size;
int& operator[](int i){return a[i];}
Highn():size(0){memset(a,0,sizeof(a));}
Highn(int x)
{
size=0;memset(a,0,sizeof(a));
while (x)
{
a[++size]+=x%F;
x/=F;
}
}
friend Highn operator*(Highn a,Highn b)
{
Highn c;
For(i,a.size)
For(j,a.size)
{
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/F;
c[i+j-1]%=F;
}
c.size=a.size+b.size;
while (c.size&&!c[c.size]) c.size--;
return c;
}
friend Highn operator*(Highn a,int b)
{
For(i,a.size) a[i]*=b;
For(i,a.size) a[i+1]+=a[i]/F,a[i]%=F;
a.size++;while (a.size&&!a[a.size]) a.size--;
return a;
}
void print()
{
printf("%d",a[size]);
ForD(i,size-1)
{
printf("%04d",a[i]);
}puts("");
}
}ans;
int v[MAXN]={0};
int main()
{
freopen("bzoj1005.in","r",stdin);
scanf("%d",&n);blank_pos=n-2;
int un_blank_pos=0;
For(i,n)
{
scanf("%d",°ree[i]);
if (degree[i]^-1)
{
if (!degree[i]&&n>1){puts("1");return 0;}
else if (!degree[i]) {puts("0");return 0;}
blank_pos-=(--degree[i]);v[degree[i]]--;un_blank_pos+=degree[i]++;
}else T++;
}
v[n-2]++;v[blank_pos]--;
// For(i,n) cout<<v[i]<<' ';cout<<endl;
_ans=mul_arr(T,blank_pos);
if (un_blank_pos+blank_pos!=n-2)
{
puts("0");return 0;
}
// cout<<blank_pos<<' '<<T<<endl;
// _ans.print();
For(i,n)
{
jc=jc+mul_arr(i,1);
// cout<<' ';jc.print();
if (v[i]) For(j,n) _ans[j]+=v[i]*jc[j];
// _ans.print();
}
// For(i,n) cout<<_ans[i]<<' ';cout<<endl;
ans=1;
For(i,n)
For(j,_ans[i])
ans=ans*i;//,ans.print();
ans.print();
return 0;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define ForD(i,n) for(int i=n;i>=1;i--)
#define MAXN (1000+10)
#define MAXLen (100000+10)
#define F (10000)
int n,degree[MAXN],T=0,blank_pos;
struct mul_arr
{
int a[MAXN];
int& operator[](int i){return a[i];}
mul_arr(){memset(a,0,sizeof(a));}
mul_arr(int m,int k) //pow(m,k)
{
memset(a,0,sizeof(a));
for(int i=2;i*i<=m;i++)
while (!(m%i))
{
a[i]+=k;m/=i;
}
if (m>1) a[m]+=k;
}
friend mul_arr operator-(mul_arr a,mul_arr b){For(i,n) a[i]-=b[i]; return a;}
friend mul_arr operator+(mul_arr a,mul_arr b){For(i,n) a[i]+=b[i]; return a;}
void print(){For(i,n) cout<<a[i]<<' ';cout<<endl;}
}_ans,jc;
struct Highn
{
int a[MAXN],size;
int& operator[](int i){return a[i];}
Highn():size(0){memset(a,0,sizeof(a));}
Highn(int x)
{
size=0;memset(a,0,sizeof(a));
while (x)
{
a[++size]+=x%F;
x/=F;
}
}
friend Highn operator*(Highn a,Highn b)
{
Highn c;
For(i,a.size)
For(j,a.size)
{
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/F;
c[i+j-1]%=F;
}
c.size=a.size+b.size;
while (c.size&&!c[c.size]) c.size--;
return c;
}
friend Highn operator*(Highn a,int b)
{
For(i,a.size) a[i]*=b;
For(i,a.size) a[i+1]+=a[i]/F,a[i]%=F;
a.size++;while (a.size&&!a[a.size]) a.size--;
return a;
}
void print()
{
printf("%d",a[size]);
ForD(i,size-1)
{
printf("%04d",a[i]);
}puts("");
}
}ans;
int v[MAXN]={0};
int main()
{
freopen("bzoj1005.in","r",stdin);
scanf("%d",&n);blank_pos=n-2;
int un_blank_pos=0;
For(i,n)
{
scanf("%d",°ree[i]);
if (degree[i]^-1)
{
if (!degree[i]&&n>1){puts("1");return 0;}
else if (!degree[i]) {puts("0");return 0;}
blank_pos-=(--degree[i]);v[degree[i]]--;un_blank_pos+=degree[i]++;
}else T++;
}
v[n-2]++;v[blank_pos]--;
// For(i,n) cout<<v[i]<<' ';cout<<endl;
_ans=mul_arr(T,blank_pos);
if (un_blank_pos+blank_pos!=n-2)
{
puts("0");return 0;
}
// cout<<blank_pos<<' '<<T<<endl;
// _ans.print();
For(i,n)
{
jc=jc+mul_arr(i,1);
// cout<<' ';jc.print();
if (v[i]) For(j,n) _ans[j]+=v[i]*jc[j];
// _ans.print();
}
// For(i,n) cout<<_ans[i]<<' ';cout<<endl;
ans=1;
For(i,n)
For(j,_ans[i])
ans=ans*i;//,ans.print();
ans.print();
return 0;
}
