[bzoj1005]：[HNOI2008]明明的烦恼（prufer序列+质因数分解+高精乘）

本文主要是介绍[bzoj1005]：[HNOI2008]明明的烦恼（prufer序列+质因数分解+高精乘），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

首先，原来我写过这个题，然而我用的别人的高精板子，然后就没有然后了。
这个故事告诉我们，千万不要用别人的板子。

好，我们开始。
首先大家都知道prufer序列这个东西吧
（没看过的可以去Matrix67那里听课：http://www.matrix67.com/blog/archives/682）
看完了之后，这个题就是组合数学了。
首先我们声明一些变量：

n->节点数
cnt->有限制节点数量
tot->无限制节点数量
d[i]->第i个节点的度数限制
sum->$\sum_{i=1}^{cnt} d[i]-1$

然后开始讲题。
首先，有cnt个点有限制，我们要从prufer序列中选出sum个位置来让他们填。
然后再用广义二项式定理，可以得出以下结论：

$$Sum_{有限制节点}=C_{n-2}^{sum}*{\frac {sum!} {\prod_{i=1}^{cnt} (d[i]-1)!}}$$ 现在我们来讨论无限制节点
首先，留给他们的位置有n-2-sum个，然而这些位置是可以随便填的
所以，又可以得出以下结论：
$$Sum_{无限制节点}=tot^{n-2-sum}$$ 所以最后的答案就是
$$Sum=Sum_{有限制节点}*Sum_{无限制节点}$$ 化简得：
$$Sum={\frac {tot^{n-2-sum}*(n-2)!} {(n-2-sum)!*\prod_{i=1}^{cnt} (d[i]-1)!}}$$ 然而要直接计算太过复杂，还要算最讨厌的除法
一个显然的结论：答案一定是整数。
所以我们就可以对分式上下两部分分解质因数，然后最后再算高精乘法就好了
关于阶乘的分解，有一种特殊的方式可以分解
具体我懒得讲了，可以看我的代码，然后自己模拟一下，就懂了。
高精比较丑，不要在意。
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=100005;
int n,cnt,sum,tot;
int prime[N],vis[N],e[N],d[N];
inline void init(){for(int i=2;i<=n;i++){if(!vis[i])prime[++cnt]=i;for(int j=1;j<=cnt&&i*prime[j]<=n;j++){vis[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
inline void mul(int x){for(int j=1;j<=cnt&&prime[j]<=x;j++){int now=prime[j];while(now<=x){e[j]+=x/now;now*=prime[j];}}
}
inline void div(int x){for(int j=1;j<=cnt&&prime[j]<=x;j++){int now=prime[j];while(now<=x){e[j]-=x/now;now*=prime[j];}}
}
int len;
ll a[N];
inline void cheng(int x){for(int i=1;i<=len;i++)a[i]*=x;for(int i=1;i<=len;i++){if(a[i]>=10){a[i+1]+=a[i]/10;a[i]%=10;}}while(a[len+1]){len++;if(a[len]>=10){a[len+1]+=a[len]/10;a[len]%=10;}}
}
int main(){n=read();init();for(int i=1;i<=n;i++){d[i]=read();if(d[i]==-1)tot++;else sum+=d[i]-1;}if(!tot&&sum!=n-2){printf("0");return 0;}if(sum>n-2){printf("0");return 0;}mul(n-2);for(int j=1;j<=cnt&&prime[j]<=tot;j++){if(tot%prime[j]==0){while(tot%prime[j]==0){e[j]+=n-2-sum;tot/=prime[j];}}}div(n-2-sum);for(int i=1;i<=n;i++)if(d[i]!=-1)div(d[i]-1);a[1]=1;len=1;for(int j=1;j<=cnt;j++){for(int k=1;k<=e[j];k++){cheng(prime[j]);}}for(int i=len;i>=1;i--)putchar(a[i]+48);return 0;
}

这篇关于[bzoj1005]：[HNOI2008]明明的烦恼（prufer序列+质因数分解+高精乘）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---