【51NOD 1806】wangyurzee的树

题目传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1806
数据生成器:http://paste.ubuntu.com/23358513/

这题知道Prufer编码的同学都能一眼秒吧?
就是裸的Prufer加上容斥。
但这题细节比较多,我说说我被坑的两个地方吧:
1)可能有多个限制条件针对一个点,在容斥的时候要排除这种情况
2)容斥的时候,所有点的度都确定了,但度数不等于n-2的情况容斥也要排除掉

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

const int M = 20;
const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;

int POW[N],REV[N],lim[M],id[M],n,m,vout,vis[N];
set<pair<int,int> > S;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int pow(int w, int t) {
	if (!w || t <= 0) return 1; int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	} return ret;
}

inline int C(int x, int y) {
	int ret = (LL)POW[y] * REV[x] % MOD;
	return (LL)ret * REV[y-x] % MOD;
}

void DFS(int t, int tot, int cnt, int sol, int f) {
	if (tot < 0 || (tot > 0 && cnt == n)) return;
	else if (t >= m + 1) {
		if (!cnt) return;
		else {
			sol = (LL)sol * pow(n - cnt,tot) % MOD;
			vout = ((vout + f*sol) % MOD + MOD) % MOD; 
		}
	} else {
		DFS(t+1, tot, cnt, sol, f);
		if (!vis[id[t]]) {
			vis[id[t]] = 1;
			DFS(t+1, tot - lim[t], cnt + 1, (LL)sol * C(lim[t],tot) % MOD, -f);
			vis[id[t]] = 0;
		}
	} 
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		id[i] = read(), lim[i] = read() - 1;
		if (S.count(make_pair(id[i],lim[i]))) {
			i--; m--;
		} else {
			S.insert(make_pair(id[i],lim[i]));
		}
	}
	POW[1] = REV[1] = POW[0] = REV[0] = 1;
	for (int i=2;i<=MX;i++) POW[i] = (LL)POW[i-1] * i % MOD;
	REV[MX] = pow(POW[MX], MOD - 2);
	for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1] * (i + 1) % MOD;
	
	vout = pow(n, n-2);
	DFS(1,n-2,0,1,1);
	printf("%d\n",vout);
	return 0;
}

【BZOJ 1005】[HNOI2008] 明明的烦恼

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1005
数据生成器:http://paste.ubuntu.com/23338303/

这题和BZOJ_1211几乎一毛一样
唯一的区别:这题要写高精 qwq
于是果断弃疗,扔一份不带高精的代码:

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

const int N = 1000+9;
const int MX = 1000;

int C[N][N],res,n,emp;
LL vout=1; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void prework(){
	C[0][0] = C[1][1] = C[0][1] = 1;
	for (int j=1;j<=MX;j++) {
		C[0][j] = 1;
		for (int i=1;i<=j;i++) {
			C[i][j] = C[i][j-1] + C[i-1][j-1];
		}
	}
}

int main(){
	if ((n=read()) == 1) {
		if (!read()) puts("1");
		else puts("1");
	} else if (n == 2) {
		if (read() == 1 && read() == 1) puts("1");
		else puts("0");
	} else {
		prework(); emp = n - 2;
		for (int i=1,tmp;i<=n;i++) {
			if ((tmp=read()) == -1) {
				res++;
			} else {
				vout *= C[tmp-1][emp];
				emp -= tmp - 1;
			}
		}
		if (emp < 0) puts("0");
		else {
			for (int i=1;i<=emp;i++) {
				vout *= res;
			}
			cout<<vout;
		}
	}
	return 0;
}

【BZOJ 1211】[HNOI2004] 树的计数

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1211
数据生成器:http://paste.ubuntu.com/23338142/

这题知道prufer编码的人做起来是大水题吧?
可以搞一搞组合数,或者直接上可重集的全排列?

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

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int C(const int &a, const int &b) {
	static int ret; ret = 1;
	for (int i=1;i<=b;i++) ret *= i;
	for (int i=1;i<=a;i++) ret /= i;
	for (int i=1;i<=b-a;i++) ret /= i;
	return ret;
}

int main(){
	int n=read();
	if (n == 1) {
		if (read() == 0) puts("1");
		else puts("0"); 
	} else if (n == 2) {
		if (read() == 1 && read() == 1) puts("1");
		else puts("0");
	} else {
		n -= 2; LL vout = 1;
		for (int i=n+2,tmp;i;i--) {
			vout *= C(tmp=read()-1,n);
			n -= tmp;
		}
		if (n == 0) cout<<vout;
		else puts("0");
	}
	return 0;
}

【BZOJ 1430】小猴打架

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1430

首先,根据Cayley公式可以得到prufer序列和生成树一一对应
于是生成树的个数就有n^(n-2)个
另外,他求的还是排列数,所以还要乘上(n-1)条边的排列

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

const int MOD = 9999991;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	int n = read(), vout = 1;
	for (int i=1;i<=n-2;i++) {
		vout = (LL)vout * n % MOD;
	}
	for (int i=n-1;i;i--) {
		vout = (LL)vout * i % MOD;
	}
	cout<<vout<<endl;
	return 0;
}