首页 > 代码库 > 【BZOJ】1005: [HNOI2008]明明的烦恼（prufer编码+特殊的技巧）
【BZOJ】1005: [HNOI2008]明明的烦恼（prufer编码+特殊的技巧）
http://www.lydsy.com/JudgeOnline/problem.php?id=1005
这里讲得挺清楚的：http://www.cnblogs.com/zhj5chengfeng/p/3278557.html
对于有n个节点的树：
prufer数列和一棵树一一对应。
prufer数列有n-2个元素
prufer数列的构造与解析：
构造：n-2步，每一步在树中查找度为1的点，并将这个点所在的边的另一个点放到prufer数列中，两个点的度均-1。
解析：将所有点的度赋值为1，然后将prufer数列的每个元素加上出现次数。n-2步，当前是第i步，找度为1的点，与prufer的第i个元素连边，两个点的度均-1。最后还剩下两个度为1的点，连边。
于是我们只需要找n-2个元素的排列方案即可。
因为只有d[i]>1的点才会出现在prufer数列中，且次数为d[i]-1，所以我们设
$$sum=\sum_{i=1}^{cnt}$$
其中$cnt$表示所有度均为已知的个数。（这里注意，度为1的点也必须算在内，因为他们必然不在prufer数列上，因此方案一一对应。）
然后我们有n-2个格子，那么可以根据多重排列知识，如果有$sum$个放到n-2个格子上，有排列数
$$\frac{sum!}{\prod_{i=1}^{cnt} (d[i]-1)!}$$
那么我们从n-2个格子选出sum个的方案有
$$\dbinom{n-2}{sum}$$
所以从n-2个取sum个的总排列有
$$\dbinom{n-2}{sum} \times \frac{sum!}{\prod_{i=1}^{cnt} (d[i]-1)!}$$
那么考虑还剩余的$n-cnt$个，因为此时还有$n-2-sum$个格子，那么考虑每一个点放在哪个格子的方案就是
$$(n-cnt)^{n-2-sum}$$
然后乘法将两个式子乘起来就是有解的方案了，可以化简为：
$$\frac{(n-2)!}{(n-2-sum)! \times \prod_{i=1}^{cnt} (d[i]-1)!} \times (n-cnt)^{n-2-sum}$$
对于无解的情况，因为只有n-2个格子，因此当sum>n-2，无解。
此外本题还要特判n=1的情况
如果暴力去解决，那么很麻烦。。根据组合知识，我们知道组合一定是能被整除的，那么我们将分子分母分解成质因数的乘积，然后指数加减最后乘起来就行了。。orz
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)const int N=1005;int prime[N], cnt, notprime[N], p[N][N], ans[N];void add(int *arr, int x, int s) { for1(i, 1, cnt) while(x%prime[i]==0) arr[i]+=s, x/=prime[i];}void add(int *h, int s) { for1(i, 1, cnt) if(h[i]) ans[i]+=s*h[i];}void init() { for1(i, 2, 1000) { if(!notprime[i]) prime[++cnt]=i; for(int j=1; j<=cnt && prime[j]*i<=1000; ++j) { notprime[prime[j]*i]=1; if(i%prime[j]==0) break; } } p[2][1]=1; for1(i, 3, 1000) { memcpy(p[i], p[i-1], sizeof(p[i])); add(p[i], i, 1); }}int n, d[N], sum, w, ans2[10005];void mul(int *a, int c) { int i=1; for(i=1; i<=a[0]; ++i) a[i]*=c; for(i=1; i<=a[0]; ++i) { a[i+1]+=a[i]/10; a[i]%=10; } while(a[i]>=10) { a[i+1]+=a[i]/10; a[i]%=10; ++i; } while(i>1 && a[i]==0) --i; a[0]=i;}void P(int *a) { for3(i, a[0], 1) printf("%d", a[i]);}int main() { read(n); if(n==1) { int x=getint(); if(x==0) puts("1"); else puts("0"); return 0; } for1(i, 1, n) { read(d[i]); if(d[i]!=-1) sum+=d[i]-1, ++w; } if(sum>n-2) { puts("0"); return 0; } init(); for1(i, 1, n-2-sum) add(ans, n-w, 1); add(p[n-2], 1); add(p[n-2-sum], -1); for1(i, 1, n) if(d[i]>1) add(p[d[i]-1], -1); ans2[0]=ans2[1]=1; for1(i, 1, cnt) while(ans[i]) mul(ans2, prime[i]), --ans[i]; P(ans2); return 0;}
Description
自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?
Input
第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1
Output
一个整数,表示不同的满足要求的树的个数,无解输出0
Sample Input
1
-1
-1
Sample Output
HINT
两棵树分别为1-2-3;1-3-2
Source
【BZOJ】1005: [HNOI2008]明明的烦恼（prufer编码+特殊的技巧）