[luogu2624 HNOI2008]明明的烦恼 (prufer+高精)

传送门

Solution

根据prufer序列做的题，具体可以看这里

还知道了一种避免高精除的方法quq

Code

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

#define R(i,a,b) for(register int i=(b);i>=(a);i--)

using namespace std;

inline int read() {

	int x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=1010,D=10000;

struct Bign{

	int da[N<<2],wei;

	Bign() {clear();}

	void out() {

		printf("%d",da[wei]);

		R(i,1,wei-1) printf("%04d",da[i]);

		putchar('\n');

	}

	void clear() {memset(da,0,sizeof(da));wei=0;}

}ans;

Bign operator*(Bign a,int b) {

	Bign res; res.wei=a.wei; int &wei=res.wei;

	F(i,1,wei) res.da[i]=a.da[i]*b;

	F(i,1,wei) res.da[i+1]+=res.da[i]/D,res.da[i]%=D;

	while(res.da[wei+1]) wei++,res.da[wei+1]=res.da[wei]/D,res.da[wei]%=D;

	return res;

}

int n,sum,cnt;

int a[N],p1[N],p2[N];

void get_p(int *p,int x) {

	int sqr=sqrt(x);

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

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

}

int main() {

	n=read();

	F(i,1,n) {

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

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

		F(j,1,a[i]-1) get_p(p2,j);

	}

	if(sum>n-2) return putchar('0'),0;

	F(i,1,n-2) get_p(p1,i);

	F(i,1,n-2-sum) get_p(p2,i),get_p(p1,n-cnt);

	F(i,1,n) p1[i]-=p2[i];

	ans.da[1]=1;ans.wei=1;

	F(i,1,n) F(j,1,p1[i]) ans=ans*i;

	ans.out();

	return 0;

}