【BZOJ1005】[HNOI2008]明明的烦恼（prufer序列）

题面

BZOJ

洛谷

题解

戳这里

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 1010

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

const int yw=10000;

struct BigNum

{

    ll s[MAX*2];int ws;

    void output()

        {

            printf("%lld",s[ws]);

            for(int i=ws-1;i;--i)

                printf("%04lld",s[i]);

            puts("");

        }

    void clear(){memset(s,0,sizeof(s));ws=0;}

}ans;

BigNum operator*(BigNum a,int b)

{

    int ws=a.ws;BigNum ret;ret.clear();

    for(int i=1;i<=ws;++i)ret.s[i]=a.s[i]*b;

    for(int i=1;i<=ws;++i)ret.s[i+1]+=ret.s[i]/yw,ret.s[i]%=yw;

    while(ret.s[ws+1])++ws,ret.s[ws+1]+=ret.s[ws]/yw,ret.s[ws]%=yw;

    ret.ws=ws;return ret;

}

int sum,a[MAX],cnt,n;

int p1[MAX],p2[MAX];

void add(int *p,int x)

{

	for(int i=2;i*i<=x;++i)

		while(x%i==0)x/=i,++p[i];

	if(x>1)++p[x];

}

int main()

{

	n=read();

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

	{

		a[i]=read();if(a[i]==-1)continue;

		++cnt;sum+=a[i]-1;

	}

	if(sum+n>2*(n-1)){puts("0");return 0;}

	for(int i=n-2;i;--i)add(p1,i);

	for(int i=n-2-sum;i;--i)add(p2,i);

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

		if(a[i]!=-1)

			for(int j=1;j<a[i];++j)

				add(p2,j);

	for(int i=1;i<=n-2-sum;++i)add(p1,n-cnt);

	for(int i=1;i<=n;++i)p1[i]-=p2[i];

	ans.s[1]=1;ans.ws=1;

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

		for(int j=1;j<=p1[i];++j)

			ans=ans*i;

	ans.output();

	return 0;

}