花都有沒有网站建设的,html网页设计基础,南京公司网站模板建站,网站建设维护与管理实训总结[BZOJ1005][HNOI2008]明明的烦恼 试题描述 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? 输入 第一行为N(0 N 1000),接下来N行,第i1行给出第i个节点的度数Di,如…[BZOJ1005][HNOI2008]明明的烦恼 试题描述 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? 输入 第一行为N(0 N 1000),接下来N行,第i1行给出第i个节点的度数Di,如果对度数不要求,则输入-1 输出 一个整数,表示不同的满足要求的树的个数,无解输出0 输入示例 3
1
-1
-1 输出示例 2 数据规模及约定 见“输入” 题解 知道 prufer 序列这题就是删边题了。这题不仅要写高精度还不能随便用除法使劲压常数组合数要分解质因数才能过 就当练高精度吧。 #include iostream
#include cstdio
#include algorithm
#include cmath
#include stack
#include vector
#include queue
#include cstring
#include string
#include map
#include set
using namespace std;const int BufferSize 1 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {if(Head Tail) {int l fread(buffer, 1, BufferSize, stdin);Tail (Head buffer) l;}return *Head;
}
int read() {int x 0, f 1; char c Getchar();while(!isdigit(c)){ if(c -) f -1; c Getchar(); }while(isdigit(c)){ x x * 10 c - 0; c Getchar(); }return x * f;
}#define maxn 1010
int n, deg[maxn], cnt;struct bign {int len, A[5010];bign() { len 1; memset(A, 0, sizeof(A)); }bign operator (const int t) {len 1; A[0] t;while(A[len-1] 9) A[len] A[len-1] / 10, A[len-1] % 10, len;return *this;}void clear() {for(; !A[len-1] len; len--) ;if(!len) len 1;return ;}bign operator * (const int t) const {bign ans; ans.len len;memcpy(ans.A, A, sizeof(A));for(int i 0; i len; i) ans.A[i] * t;for(int i 0; i len; i) ans.A[i1] ans.A[i] / 10, ans.A[i] % 10;int j len 1;for(; ans.A[j-1] 9;) ans.A[j] ans.A[j-1] / 10, ans.A[j-1] % 10, j;ans.len j;ans.clear();return ans;}bign operator * (const int t) {*this *this * t;return *this;}bign operator * (const bign t) const {bign ans; ans.len len t.len - 1;for(int i 0; i len; i)for(int j 0; j t.len; j) ans.A[ij] A[i] * t.A[j];for(int i 0; i ans.len; i) ans.A[i1] ans.A[i] / 10, ans.A[i] % 10;int j ans.len 1;for(; ans.A[j-1] 9;) ans.A[j] ans.A[j-1] / 10, ans.A[j-1] % 10, j;ans.len j;ans.clear();return ans;}bign operator * (const bign t) {*this *this * t;return *this;}bign operator - (const bign t) const {bign ans; ans.len len;memcpy(ans.A, A, sizeof(A));for(int i 0; i len; i) {if(i t.len) ans.A[i] - t.A[i];if(ans.A[i] 0) ans.A[i] 10, ans.A[i1]--;}while(!ans.A[ans.len-1]) ans.len--;return ans;}bign operator - (const bign t) {*this *this - t;return *this;}bign operator / (const bign t) const {bign ans, f; f 0; ans.len -1;for(int i len - 1; i 0; i--) {f * 10;f.A[0] A[i];while(f t) {f - t;ans.A[i];if(ans.len -1) ans.len i 1;}}return ans;}bool operator (const bign t) const {if(len ! t.len) return len t.len;for(int i len - 1; i 0; i--) if(A[i] ! t.A[i]) return A[i] t.A[i];return 1;}void print() {for(int i len - 1; i 0; i--) putchar(A[i] 0);return ;}
} ;int prime[maxn], cp;
bool vis[maxn];
void prime_table() {for(int i 2; i n; i) {if(!vis[i]) prime[cp] i;for(int j 1; j cp i * prime[j] n; j) {vis[i*prime[j]] 1;if(i % prime[j] 0) break;}}return ;
}
bign Pow(int a, int n) {bign sum, t; sum 1; t a;while(n) {if(n 1) sum * t;t * t; n 1;}return sum;
}
int Cp[maxn];
bign C(int n, int m) {for(int i 1; i cp; i) Cp[i] 0;for(int i n; i n - m 1; i--) {int tmp i;for(int j 1; j cp; j) if(tmp % prime[j] 0)while(tmp % prime[j] 0) Cp[j], tmp / prime[j];}for(int i m; i; i--) {int tmp i;for(int j 1; j cp; j) if(tmp % prime[j] 0)while(tmp % prime[j] 0) Cp[j]--, tmp / prime[j];}bign sum; sum 1;for(int i 1; i cp; i) if(Cp[i]) sum * Pow(prime[i], Cp[i]);return sum;
}int main() {n read();prime_table();int tot 0;bool ok 1;for(int i 1; i n; i) {int x read();if(x 0) deg[cnt] x - 1, tot (x - 1);if(!x) ok 0;}if(!ok || tot n - 2) return puts(0), 0;tot n - 2;bign sum; sum 1;for(int i 1; i cnt; i) {sum * C(tot, deg[i]);tot - deg[i];}sum * Pow(n - cnt, tot);sum.print(); putchar(\n);return 0;
}除法的定义其实没用我第一次用了除法 T 飞了现在懒得删了。转载于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/5743709.html
