BZOJ 1005: [HNOI2008]明明的烦恼(高精度+prufer序)

解题思路

　　看到度数和生成树个树，可以想到$prufer$序，而一张规定度数的图的生成树个数为$\frac{(n-2)!}{\prod\limits_^{n(d(i)-1)!}$。而这道题有的度数没有限制，那就设有度数限制的点的个数为$num$，$\sum (d_i-1)$为$sum$。把这些点先填入$prufer$序中，其余没有限制的点可以随便填，再乘上组合数，答案应该为$C(n-2,sum)\frac{(sum!}{\prod (d_i-1)!}(n-cnt)}$，把组合数展开得$\frac{(n-2)!}{(n-2-sum)!*\prod(d_i-1)!} *(n-cnt)^$。避免写高精除，可以把他们质因数分解，然后高精乘。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int N=6005;

int n,prime[N],cnt,d[N],tot[N],sum;

bool vis[N];

struct bign{

	int a[N],len;

	bign mul(bign A,int B){

		for(int i=1;i<=A.len;i++) A.a[i]*=B;

		for(int i=1;i<=A.len;i++)

			A.a[i+1]+=A.a[i]/10,A.a[i]%=10;

		while(A.a[A.len+1]) {

			A.len++; A.a[A.len+1]+=A.a[A.len]/10;

			A.a[A.len]%=10;

		}

		return A;

	}

}ANS;

inline void prework(){

	for(int i=2;i<=1000;i++){

		if(!vis[i]) prime[++cnt]=i;

		for(int j=1;j<=cnt && i*prime[j]<=1000;j++)

			vis[i*prime[j]]=1;

	}

}

inline void work(int x,int k){

	for(int i=1;i<=cnt;i++){

		if(prime[i]>x) return ;

		while(!(x%prime[i])) tot[i]+=k,x/=prime[i];

	}

}

int main(){

	scanf("%d",&n); prework(); int num=0;

  	for(int i=2;i<=n-2;i++) work(i,1);

	for(int i=1;i<=n;i++) {

		scanf("%d",&d[i]);

		if(d[i]==-1) continue;

		sum+=d[i]-1; num++;

		for(int j=2;j<d[i];j++) work(j,-1);

	}

	for(int i=2;i<=n-2-sum;i++) work(i,-1);

	work(n-num,n-2-sum); ANS.len=1; ANS.a[1]=1;

	for(int i=1;i<=cnt;i++)

		while(tot[i]--) ANS=ANS.mul(ANS,prime[i]);

	for(int i=ANS.len;i;i--) printf("%d",ANS.a[i]);

	return 0;

}

巴特西

BZOJ 1005: [HNOI2008]明明的烦恼(高精度+prufer序)

解题思路

代码

最新文章

热门文章