INOI2021 Day2T3 Andarzgu

来源

https://www.noi.cn/xw/2021-05-31/729403.shtml

题意

给定一张 (n) 个点、(m) 条边的有向图，你需要选出一些点集互不相交的简单环（可以一个都不选），使得存在一种这些环的排列方式，存在一个点 (s)，从 (s) 出发可以依次遍历这些环的所有点（注意，每个点可以经过多次，从一个环到下一个环经过的点没有要求）。

求选环的方案数的奇偶性。

(n leq 5000, m leq min left(10^6, inom n 2 ight))。无重边无自环。

子任务：

忽略边的方向后，这张图是仙人掌。
这张图是强连通图。

题解

考虑子任务 2 怎么做。

选若干环的方案可以唯一映射到一个排列（毕竟排列可以分解为若干不相交的环，选择 ((u,v)) 则排列中 (p_u=v)，没选到的点则 (p_i=i)），且这个映射是个单射（不同的方案对应不同的排列）。

那么只要数出合法的排列数（可以被映射到的排列数）即可。显然，排列合法当且仅当 ((i,p_i)in E)，我们就在选环的方案和这些排列之间建立了双射。

即方案数就是邻接矩阵 (A) 加上单位矩阵 (I_n) 的积和式：

[operatorname{perm}left( A+I_n ight)=sum_{pin operatorname{permutation(n)}} prod_{i=1}^n (A+I_n)_{i,p_i} ]

计算积和式是难以解决的。而我们只关心奇偶性，因此只要计算行列式的奇偶性（(sigma(p)) 表示 (p) 的逆序对数）：

[detleft(A+I_n ight)=sum_{pin operatorname{permutation(n)}} (-1)^{sigma(p)}prod_{i=1}^n left( A+I_n ight)_{i,p_i} ]

用 bitset 压位即可做到 (mathcal Oleft(frac{n^3}{omega}+n^2 ight)) 计算行列式。

对于一般图，我们只要将每个强连通分量运行如上算法得到方案数奇偶性，缩点后再按照拓扑序 DP 即可，用 bitset 实现传递闭包来处理转移合法性的判断。

时间复杂度 (mathcal O left( frac{n^3}{omega}+n^2+m ight))

#include <bits/stdc++.h>

using namespace std; 

template <class T>
inline void read(T &x) {
	static char ch; 
	while (!isdigit(ch = getchar())); 
	x = ch - '0'; 
	while (isdigit(ch = getchar()))
		x = x * 10 + ch - '0'; 
}

template <class T>
inline void tense(T &x, const T &y) {
	if (x > y) x = y; 
}

const int MaxN = 5000 + 5; 

int n, m; 
bool adj[MaxN][MaxN]; 

int dfsClock, dfn[MaxN], low[MaxN]; 
int top, stk[MaxN]; 

int nScc, scc[MaxN], valScc[MaxN]; 
vector<int> verScc[MaxN]; 

bitset<5000> mat[5000]; 

int det(int n) {
	for (int i = 0; i < n; ++i) {
		int p = -1; 
		for (int j = i; j < n; ++j)
			if (mat[j][i]) {
				p = j; 
				break; 
			}
		
		if (p == -1)
			return 0; 
		if (p != i)
			swap(mat[i], mat[p]); 

		for (int j = i + 1; j < n; ++j)
			if (mat[j][i]) {
				mat[j] ^= mat[i]; 
			}
	}

	return 1; 
}

void tarjan(int u) {
	stk[++top] = u; 
	dfn[u] = low[u] = ++dfsClock; 

	for (int v = 1; v <= n; ++v)
		if (adj[u][v]) {
			if (!dfn[v]) {
				tarjan(v); 
				tense(low[u], low[v]); 
			} else if (!scc[v]) {
				tense(low[u], dfn[v]); 
			}
		}
	
	if (dfn[u] == low[u]) {
		++nScc; 

		do {
			int v = stk[top--]; 
			scc[v] = nScc; 
			verScc[nScc].push_back(v); 

			// cerr << v << ' '; //
		} while (stk[top + 1] != u); 

		vector<int> &V = verScc[nScc]; 
		for (int i = 0; i < (int)V.size(); ++i) {
			mat[i].reset(); 
			for (int j = 0; (int)j < V.size(); ++j)
				mat[i][j] = adj[V[i]][V[j]]; 
			mat[i][i] = 1; 
		}

		valScc[nScc] = det(V.size()) ^ 1; 
	}
}

int main() {
#ifdef orzczk
	freopen("andarzgu.in", "r", stdin); 
	freopen("andarzgu.out", "w", stdout); 
#endif

	read(n), read(m); 
	for (int i = 1; i <= m; ++i) {
		int u, v; 
		read(u), read(v); 

		assert(u != v); 
		assert(!adj[u][v]); 

		adj[u][v] = 1; 
	}

	for (int i = 1; i <= n; ++i)
		if (!dfn[i])
			tarjan(i); 

	int res = 1; 
	static int f[MaxN]; 
	static bitset<MaxN> vis[MaxN]; 

	for (int i = nScc; i >= 1; --i) {
		vis[i][i] = 1; 
		for (int u : verScc[i]) {
			for (int v = 1; v <= n; ++v)
				if (adj[v][u] && scc[v] != scc[u]) {
					vis[i] |= vis[scc[v]]; 
				}
		}

		f[i] = valScc[i]; 
		if (valScc[i]) {
			for (int j = i + 1; j <= nScc; ++j)
				if (vis[i][j])
					f[i] ^= f[j]; 
		}

		res ^= f[i]; 
	}

	puts(res ? "Mistletoe: Time to go home!" : "Daddy: We should have a date..."); 

	return 0; 
}