prufer编码+高精度
推荐阅读：Prüfer编码与Cayley公式
还记得自己很久以前也想过有没有某种序列能和树一一对应的，原来是有的。
显然一个性质：度数为m的节点的序号在prufer编码中出现的次数为m-1。
所以把带限制的度数用组合数暴力算一下，没限制也算一下即可。注意这题答案很大，要用高精度。把代码里乘法除法全都改成质因数加减的形式就行了。
想+写没花多久，主要死在高精度上orz。数组开太大会T，开小了又WA，开成longlong又T。。。优化了一下才过
#include<cstdio> #include<cstring> #include<algorithm> #define N 1005 #define BASE 1000000 using namespace std; namespace runzhe2000 { int deg[N], prime[N], notprime[N], pcnt, cnt[N]; struct bigint { long long num[555]; int len; bigint(int x = 0) { memset(num,0,sizeof(num)); num[0] = x; len = 1; for(; num[len-1] >= BASE; ) { num[len] = num[len-1] / BASE; num[len-1] %= BASE; len++; } } bigint operator * (bigint that) { bigint r; for(int i = 0; i < len; i++) for(int j = 0; j < that.len; j++) r.num[i+j] += num[i] * that.num[j]; r.len = len + that.len - 1; for(int i = 0; i < r.len; i++) { r.num[i+1] += r.num[i] / BASE; r.num[i] %= BASE; } if(r.num[r.len])r.len++; return r; } void print() { printf("%lld",num[--len]); for(len--; ~len; len--) printf("lld",num[len]); puts(""); } }; bigint fpow(bigint a, int b) { bigint r = 1; for(; b; b>>=1) { if(b&1) r=r*a; a=a*a; } return r; } void make(int a, int v) { if(!v) return; for(int i = 1; i <= pcnt; i++) for(; a % prime[i] == 0; a /= prime[i]) cnt[i] += v; } void makefac(int a, int v) { for(int i = 1; i <= pcnt; i++) { int tmp = a; for(; tmp >= prime[i]; ) { cnt[i] += v * tmp / prime[i]; tmp /= prime[i]; } } } void init_prime(int n) { for(int i = 2; i <= n; i++) { if(!notprime[i]) prime[++pcnt] = i; for(int j = 1; j <= pcnt && prime[j] * i <= n; j++) { notprime[prime[j] * i] = 1; if(i % prime[j] == 0) break; } } } void main() { int n, last, free = 0; scanf("%d",&n); init_prime(n); last = n - 2; for(int i = 1; i <= n; i++) { scanf("%d",°[i]); if(deg[i] == -1) free++; else if(!deg[i] && n != 1){puts("0"); return;} } for(int j = 1; j <= n; j++) { if(deg[j] != -1) { int tmp = deg[j] - 1; if(last < tmp) {last = -1; break;} makefac(last,1); makefac(tmp,-1); makefac(last-tmp,-1); last -= tmp; } } if(last < 0) puts("0"); else { bigint now = 1; make(free,last); for(int i = 1; i <= pcnt; i++) now = now * fpow(prime[i], cnt[i]); now.print(); } } } int main() { runzhe2000::main(); }