【日常小测】学外语

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞

Code

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

const int N = 1000009;
const int MOD = 1000000007;
const int INF = 2e9;

int n, E, ans, head[N], nxt[N], to[N];
int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N];
int pre[N], dep[N], in[N], deg[N], vis[N];

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

inline int Pow(int w, int t) {
	int ret = 1;
	for (; t; t >>= 1, w = (LL)w * w % MOD) {
		if (t & 1) {
			ret = (LL)ret * w % MOD;
		}
	}
	return ret;
}

inline void AddEdge(int u, int v) {
	in[v]++; deg[v]++; pre[u] = v;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void mrk(int w) {
	vis[w] = 1;
	if (--in[pre[w]] == 0) {
		mrk(pre[w]);
	}
}

inline int cal_node(int w) {
	int ret = R2[deg[w]];
	vector<int> arr;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!in[to[i]]) {
			dep[to[i]] = dep[w] + 1;
			int tmp = cal_node(to[i]);
			arr.push_back(tmp);
			ret = (ret + (LL)R1[dep[w]] * tmp) % MOD;
		}
	}
	sort(arr.begin(), arr.end());
	for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
		for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
		ans = (LL)ans * ipw[j - i + 1] % MOD;
	}
	return (LL)ret * ret % MOD;
}

inline int cal_cir(int w) {
	vector<int> node, arr;
	while (!vis[w]) {
		vis[w] = 1;
		node.push_back(w);
		for (int i = head[w]; i; i = nxt[i]) {
			if (in[to[i]]) {
				w = to[i];
				break;
			}
		}
	}
	for (int i = 0; i < (int)node.size(); i++) {
		dep[node[i]] = 6;
		arr.push_back(cal_node(node[i]));
	}
	int sta = 0, cnt = 1;
	for (int i = 0; i < (int)node.size(); i++) {
		sta = (sta + (LL)pw23[i] * arr[i]) % MOD;
	} 
	int ret = (LL)sta * pw23[n] % MOD;
	for (int i = 1, cur = sta; i < (int)node.size(); i++) {
		cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD;
		ret = min(ret, int((LL)cur * pw23[n - i] % MOD));
		cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD);
	}
	ans = (LL)ans * inv[cnt] % MOD;
	return ret;
}

int main() {
	srand(19991216);
	inv[0] = pw[0] = ipw[0] = pw23[0] = 1;
	R1[0] = rand(); R2[0] = rand();
	for (int i = 1; i < N; i++) {
		pw[i] = (LL)pw[i - 1] * i % MOD;
		pw23[i] = pw23[i - 1] * 131ll % MOD;
		inv[i] = Pow(i, MOD - 2);
		ipw[i] = Pow(pw[i], MOD - 2);
		R1[i] = rand(); R2[i] = rand();
	}
	
	for (int T = read(); T; T--) {
		memset(head, 0, sizeof(head));
		memset(deg, 0, sizeof(deg));
		memset(vis, 0, sizeof(vis));
		memset(in, 0, sizeof(in));
		E = 0; ans = 1;
		
		n = read();
		for (int i = 1; i <= n; i++) {
			AddEdge(i, read());
		}	
		for (int i = 1; i <= n; i++) {
			if (!in[i] && !vis[i]) {
				mrk(i);
			}
		}
		vector<int> arr;
		for (int i = 1; i <= n; i++) {
			if (in[i] && !vis[i]) {
				arr.push_back(cal_cir(i));
			}
		}
		sort(arr.begin(), arr.end());
		for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) {
			for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j);
			ans = (LL)ans * ipw[j - i + 1] % MOD;
		}
		ans = ((LL)ans * pw[n] - 1) % MOD;
		printf("%d\n", (ans + MOD) % MOD);
	}
	return 0;
}

【BZOJ 1040】[ZJOI2008] 骑士

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1040
数据生成器:http://paste.ubuntu.com/23618220/
神犇题解:http://blog.csdn.net/popoqqq/article/details/39748135

题解

看到这个题,感觉除了网络流之外别无他法
结果这货是个基环森林啊!
I well vegetable are!

这个问题搬到树上去大家都会做
原题好像叫“没有上司的舞会”?
考虑给树加上一条边之后会发生什么变化:
这条非树边要么两段的点选一个,要么都不选
于是特殊处理一下,跑三遍树上DP就可以辣!

Code

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

const int N = 1000000+9;
const int M = N << 1;

int head[N],to[M],nxt[M];
int n,val[N],aim[N],tag[N],lb,rb;
LL vout,f[N][2];

inline void Add_Edge(const int u, const int v) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

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;
}

void DFS(int w, int f) {
	tag[w] = 1; 
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f && to[i]) {
		if (tag[to[i]]) {
			lb = w; rb = to[i];
			to[i] = to[i^1] = 0;
		} else {
			DFS(to[i], w);
		}
	}
}
 
void solve(int w, int fa) {
	f[w][0] = 0;
	f[w][1] = val[w];
	for (int i=head[w];i;i=nxt[i]) if (to[i] && to[i] != fa) {
		solve(to[i], w);
		f[w][1] += f[to[i]][0];
		f[w][0] += max(f[to[i]][1],f[to[i]][0]);
	}
	if (tag[w] == 2) {
		f[w][0] = 0;
	} else if (tag[w] == 3) {
		f[w][1] = 0;
	}
}
 
int main(){
	n = read();
	for (int i=1,t;i<=n;i++) {
		val[i] = read();
		if (aim[t=read()] != i) {
			Add_Edge(i, t);
			aim[i] = t;
		}
	}
	for (int i=1;i<=n;i++) {
		if (!tag[i]) {
			LL tmp; 
			lb = rb = 0;
			DFS(i,i);
			
			tag[lb] = 2; tag = 3;
			solve(i,i);
			tmp = max(f[i][0], f[i][1]);
			
			tag[lb] = 3; tag = 2;
			solve(i,i);
			tmp = max(tmp, max(f[i][0], f[i][1]));
			
			tag[lb] = 3; tag = 3;
			solve(i,i);
			tmp = max(tmp, max(f[i][0], f[i][1]));
			vout += tmp;
		}
	}
	printf("%lld\n",vout);
	return 0;
}