[HNOI2008] 明明的烦恼

Description

给定部分顶点的度，求有多少棵符合条件的有标号无根树。(n le 1000)

Solution

首先将度确定者填入，则剩余位置可以任意填入度不确定者，故方案数为

[C_{n-2}^{tot}C_{tot}^{d_1-1}C_{tot-(d_1-1)}^{d_2-1} dots m^{n-2-tot} ]

其中 (tot) 为既定的 (d_i-1) 总和，(m) 为度不定的点个数，展开化简得

[frac {(n-2)!} {(n-2-tot)!(d_1-1)!(d_2-1)! dots(d_n-1)!} m^{n-2-tot} ]

暴力算要写高精除法，考虑到数字都不大，用桶记录质因子，最后高精乘即可

#include <bits/stdc++.h>
using namespace std;

#define int long long


struct Biguint {
	int a[20005], len;

	Biguint() {
		memset(a, 0, sizeof a);
		len = 0;
	}

	void read(string str) {
		memset(a, 0, sizeof a);
		len = str.length();
		for (int i = 0; i < str.size(); i++)
			a[i] = str[str.length() - i - 1] - '0';
	}

	void print() {
		for (int i = len - 1; i >= 0; i--) {
			cout << a[i];
		}
	}

	bool operator < (const Biguint& obj) {
		const int* b = obj.a;
		if (this->len == obj.len) {
			for (int i = len-1; i>=0; --i)
				if (a[i] != b[i]) return a[i] < b[i];
			return false;
		}
		else return this->len < obj.len;
	}

	bool operator > (const Biguint& obj) {
		const int* b = obj.a;
		if (this->len == obj.len) {
			for (int i = len-1; i>=0; --i)
				if (a[i] != b[i]) return a[i] > b[i];
			return false;
		}
		else return this->len > obj.len;
	}

	bool operator != (const Biguint& obj) {
		return (*this < obj) | (*this > obj);
	}

	bool operator == (const Biguint& obj) {
		return !((*this < obj) | (*this > obj));
	}

	bool operator <= (const Biguint& obj) {
		return (*this) < obj || (*this) == obj;
	}

	bool operator >= (const Biguint& obj) {
		return (*this) > obj || (*this) == obj;
	}

	Biguint operator += (const Biguint& obj) {
		const int* b = obj.a;
		if (obj.len > len) len = obj.len;
		for (int i = 0; i < len; i++) {
			a[i] += b[i];
			if (a[i] >= 10) a[i + 1] += a[i] / 10, a[i] %= 10;
		}
		if (a[len]) ++len;
		while (a[len - 1] >= 10)
			a[len] += a[len - 1] / 10, a[len - 1] %= 10, ++len;
		return *this;
	}

	Biguint operator + (const Biguint& obj) {
		Biguint ret;
		ret += *this;
		ret += obj;
		return ret;
	}

	Biguint operator -= (const Biguint& obj) {
		const int* b = obj.a;
		for (int i = 0; i < len; i++) {
			a[i] -= b[i];
			if (a[i] < 0) a[i + 1]--, a[i] += 10;
		}
		while (a[len - 1] == 0 && len > 0) --len;
		return *this;
	}

	Biguint operator -(const Biguint& obj) {
		Biguint ret;
		ret += *this;
		ret -= obj;
		return ret;
	}

	Biguint operator *= (int b) {
		for (int i = 0; i < len; i++)
			a[i] *= b;
		for (int i = 0; i < len; i++)
			a[i + 1] += a[i] / 10, a[i] %= 10;
		++len;
		while (a[len - 1] >= 10)
			a[len] += a[len - 1] / 10, a[len - 1] %= 10, ++len;
		while (a[len - 1] == 0 && len > 0) --len;
		return *this;
	}

	Biguint operator * (int b) {
		Biguint ret;
		ret = *this;
		ret *= b;
		return ret;
	}

	Biguint operator * (const Biguint& obj) {
		const int* b = obj.a;
		Biguint ret;
		for (int i = 0; i < len; i++)
			for (int j = 0; j < obj.len; j++)
				ret.a[i + j] += a[i] * b[j];
		for (int i = 0; i < len + obj.len; i++)
			ret.a[i + 1] += ret.a[i] / 10, ret.a[i] %= 10;
		ret.len = len + obj.len;
		++ret.len;
		while (ret.a[ret.len - 1])
			ret.a[ret.len] += ret.a[ret.len - 1] / 10, ret.a[ret.len - 1] %= 10, ++ret.len;
		while (ret.a[ret.len - 1] == 0 && ret.len > 0) --ret.len;
		return ret;
	}

};

const int N = 1005;

int b[N];

void bucket_mul(int x)
{
    for(int i=2;i<=40;i++)
    {
        while(x%i==0)
        {
            x/=i;
            b[i]++;
        }
    }
    if(x>1) b[x]++;
}

void bucket_div(int x)
{
    for(int i=2;i<=40;i++)
    {
        while(x%i==0)
        {
            x/=i;
            b[i]--;
        }
    }
    if(x>1) b[x]--;
}

int n,d[N];

ostream& operator << (ostream& os, Biguint num)
{
	for (int i = num.len - 1; i >= 0; --i)
		os << num.a[i];
	if (num.len == 0) os << "0";
	return os;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>d[i];

    int tot=0,m=0;
    for(int i=1;i<=n;i++) if(d[i]!=-1) tot+=d[i]-1;
    for(int i=1;i<=n;i++) m+=(d[i]==-1);

    for(int i=1;i<=n-2;i++) bucket_mul(i);
    for(int i=1;i<=n-2-tot;i++) bucket_mul(m);
    for(int i=1;i<=n-2-tot;i++) bucket_div(i);
    for(int i=1;i<=n;i++) if(d[i]!=-1)
    {
        for(int j=1;j<=d[i]-1;j++) bucket_div(j);
    }

    Biguint ans;
    ans.read("1");
    for(int i=1;i<=n;i++)
    {
        while(b[i])
        {
            b[i]--;
            ans*=i;
        }
    }

    cout<<ans<<endl;
}