该题运用到了树的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!可分解为 一个数*
，其中
且
<n
，其中且 <n
所以 
暴力分解：
1 //模仿CLJ大神写的STL,并学会了各种写代码技巧，长见识了！ 2 #include<iostream> 3 #include<cstring> 4 #include<string.h> 5 #include<algorithm> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 10 int n,nolimit=0,tot=0,ans[10005]={0}; 11 12 vector<int> prime; 13 14 typedef struct{ 15 int h[400]; 16 void Init(){memset(h,0,sizeof(h));} 17 18 void mul(int x){ 19 for(int i=0;i<prime.size();++i) 20 while(x%prime[i]==0) 21 {h[i]++;x/=prime[i];} 22 } 23 void div(int x){ 24 for(int i=0;i<prime.size();++i) 25 while(x%prime[i]==0) 26 {h[i]--;x/=prime[i];} 27 } 28 29 }typenum;typenum sum; 30 31 bool Isprime(int x){ 32 int i; 33 for(i=2;i<=sqrt(x);++i) 34 if(x%i==0) return 0; 35 return 1; 36 } 37 38 void Makeprime(){ 39 for(int i=2;i<=n;++i) 40 if(Isprime(i)) prime.push_back(i); 41 return ; 42 } 43 44 void Init(){ 45 cin>>n; 46 Makeprime(); 47 // for(int i=0;i<prime.size();++i) 48 // cout<<prime[i]<<" ";cout<<endl; 49 sum.Init(); 50 // for(int i=0;i<400;++i) 51 // cout<<sum.h[i]<<" "; 52 int d; 53 for(int i=1;i<=n;++i) 54 { 55 cin>>d; 56 57 for(int i=1;i<d;++i) 58 sum.div(i); 59 if(d==-1)nolimit++;///注意 60 else tot+=d-1;////注意 61 } 62 } 63 64 void Work(){ 65 if(tot>n-2||(tot!=n-2&&nolimit==0)) {cout<<0<<endl;return ;} 66 67 for(int i=1;i<=n-2;++i) 68 sum.mul(i); 69 70 for(int i=1;i<=n-2-tot;++i) 71 sum.div(i); 72 73 for(int i=1;i<=n-2-tot;++i) 74 sum.mul(nolimit); 75 76 ans[0]=1; 77 for(int i=0;i<prime.size();++i) 78 while(sum.h[i]>0) 79 { 80 sum.h[i]--; 81 for(int j=0;j<10000;++j) 82 ans[j]*=prime[i]; 83 84 for(int j=0;j<10000;++j) 85 if(ans[j]>9) 86 {ans[j+1]+=ans[j]/10;ans[j]%=10;} 87 } 88 89 int i=10000; 90 while(ans[i]==0) i--; 91 while(i>=0) cout<<ans[i--]; 92 cout<<endl; 93 } 94 95 int main() 96 { 97 Init(); 98 Work(); 99 // Print(); 100 // system("pause"); 101 return 0; 102 }
n!质因数特殊分解：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string.h> 5 #include<cstdlib> 6 #include<cmath> 7 #include<fstream> 8 using namespace std; 9 //ifstream cin("cin.in"); 10 11 int n,m=0,tot=0,fenmu[1005]={0},fenzi[1005]={0},prime[1005]={0}; 12 int ans[10005]={0}; 13 14 void Fenjie(int zz,int a[]){ 15 int sum; 16 for(int i=2;i<=zz;++i) 17 if(prime[i]) 18 { 19 sum=i; 20 while(sum<=zz) 21 {a[i]+=zz/sum;sum*=i;} 22 } 23 return ; 24 } 25 26 void Buildprime(){ 27 int i,j; 28 for(i=2;i<=1000;++i) 29 { 30 for(j=2;j<=sqrt(i);++j) 31 if(i%j==0) break; 32 if(j>sqrt(i)) prime[i]=1;//,cout<<i<<" "; 33 }//cout<<endl; 34 } 35 36 int main() 37 { 38 cin>>n; 39 40 Buildprime(); 41 42 for(int i=1;i<=n;++i) 43 { 44 int d; 45 cin>>d; 46 if(d==-1) {m++;continue;} 47 if(d>1) Fenjie(d-1,fenmu); 48 tot+=d-1; 49 } 50 51 Fenjie(n-2-tot,fenmu); 52 Fenjie(n-2,fenzi); 53 54 for(int i=1;i<=1000;++i) 55 fenzi[i]-=fenmu[i]; 56 57 ans[0]=1; 58 59 for(int i=1;i<=1000;++i) 60 while(fenzi[i]>0) 61 { 62 fenzi[i]--; 63 for(int j=0;j<=10000;++j) 64 ans[j]*=i; 65 for(int j=0;j<=10000;++j) 66 if(ans[j]>9) 67 {ans[j+1]+=ans[j]/10;ans[j]%=10;} 68 } 69 70 if(m>0) 71 for(int i=1;i<=n-2-tot;++i) 72 { 73 for(int j=0;j<=10000;++j) 74 ans[j]*=m; 75 for(int j=0;j<=10000;++j) 76 if(ans[j]>9) 77 { 78 ans[j+1]+=ans[j]/10; 79 ans[j]%=10; 80 } 81 } 82 83 if(tot>n-2||(tot<n-2&&m==0)) {cout<<0<<endl;return 0;} 84 85 int i=10000; 86 while(ans[i]==0) i--; 87 // if(i<=0) cout<<ans[0]; 88 while(i>=0) cout<<ans[i--]; 89 cout<<endl; 90 91 // system("pause"); 92 return 0; 93 94 }
京公网安备 11010502036488号