「ARC083」F - Collecting Balls - 基环树 + 思维

有一个 $n\times n$ 的矩阵，矩阵内有 $2n$ 个球。对于 $i \in [1,n]$ ，$(0,i) (i,0)$ 的位置各有一个启动后往右走/往上走的机器人，机器人撞到球会和球一起消失。问启动机器人顺序的方案数，满足所有球最后都消失。

$n \le 10^{5}$

Link

ARC083F

Solution

把球看成点，机器人看成边。若存在一个$(x, y)$的球，则连$(x, y + n)$，权值为$x + y$的边

这样连边后，每选择一个点就会拿掉它相邻剩下的边权最小的边；拿掉一条边就代表这个机器人撞没了

并且必须要保证一个点对应一条边

因为只有$n$个点$n$条边，所以一定是一个基环树森林（否则无解）。显然，基环树的每个子树的方案是确定的（从叶子往根推，只有一种方案），并且环上也只有两种方案（每条边属于左边的点或是右边的点）。可以枚举这两种情况算答案

此时每个点已经分配了一个边权，但仍然有一些限制关系，即对于某个点分配到的那条边而言，所有与之相连且边权更小的边，必须要先选。显然，这样的限制又构成一棵森林

问题便转化为，求一个选择序列使得所有点的祖先比它自己先选择，是一个经典问题

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;
const int Mod = 1e9 + 7;


namespace MATH
{
	int fac[Maxn], ifac[Maxn];

	inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
		return ans;
	}

	inline void init (int n = 2e5)
	{
		fac[0] = 1;
		for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % Mod;
		ifac[n] = Pow (fac[n], Mod - 2);
		for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % Mod;
	}

	inline int C (int n, int m) { if (n < m) return 0; return (LL) fac[n] * ifac[m] % Mod * ifac[n - m] % Mod; }
}

using namespace MATH;

int N;
int e, Begin[Maxn], Next[Maxn << 1], To[Maxn << 1], W[Maxn << 1];

inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

inline int merge (int a, int b) { return C (a + b, b); }

int Vis[Maxn], top, in_stk[Maxn];
pii stk[Maxn];

int found;
int circle[Maxn], in_circle[Maxn];
int val_cir[Maxn];

inline void dfs_circle (int x, int f, int w)
{
	if (found) return ;
	stk[++top] = mp (x, w), in_stk[x] = 1;

	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == f) continue;
		if (!in_stk[y]) dfs_circle (y, x, W[i]);
		else
		{
			val_cir[++circle[0]] = W[i];
			while (top)
			{
				int a = stk[top].x, b = stk[top].y; --top;
				circle[circle[0]] = a;
				in_circle[a] = 1;
				val_cir[++circle[0]] = b;
				if (a == y) break;
			}
			--circle[0];
			found = 1;
			return ;
		}
		if (found) return ;
	}

	--top, in_stk[x] = 0;
}

int val[Maxn], tree[Maxn];

inline void dfs_tree (int x, int f)
{
	tree[++tree[0]] = x;
	Vis[x] = 1;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (y == f || in_circle[y]) continue;
		val[y] = W[i];
		dfs_tree (y, x);
	}
}

int fa[Maxn], size[Maxn];

inline int dfs_calc (int x)
{
	int ans = 1;
	size[x] = 0;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		if (x != fa[y]) continue;
		int now = dfs_calc (y);
		ans = (LL) ans * now % Mod * merge (size[x], size[y]) % Mod;
		size[x] += size[y];
	}
	++size[x];
	return ans;
}

inline int Calc ()
{
	for (int t = 1; t <= tree[0]; ++t)
	{
		int x = tree[t];
		fa[x] = size[x] = 0;
	}

	for (int t = 1; t <= tree[0]; ++t) 
	{
		int x = tree[t];
		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (W[i] < val[x]) fa[y] = x;
		}
	}

	int ans = 1, sum_point = 0;
	for (int t = 1; t <= tree[0]; ++t)
	{
		int x = tree[t];
		if (!fa[x])
		{
			int now = dfs_calc (x);
			ans = (LL) ans * now % Mod * merge (sum_point, size[x]) % Mod;
			sum_point += size[x];
		}
	}

	return ans;
}

inline int Process (int x)
{
	found = circle[0] = top = 0;
	dfs_circle (x, 0, 0);
	tree[0] = 0;
	for (int i = 1; i <= circle[0]; ++i) dfs_tree (circle[i], 0);

	int ans = 0;
	for (int i = 1; i <= circle[0]; ++i) val[circle[i]] = val_cir[i];
	Add (ans, Calc ());

	val_cir[circle[0] + 1] = val_cir[1];
	for (int i = 1; i <= circle[0]; ++i) val[circle[i]] = val_cir[i + 1];
	Add (ans, Calc ());

	return ans;
}

int Choose[Maxn];

inline void Solve ()
{
	int chosen = 0;
	for (int i = 1; i <= 2 * N; ++i) if (Choose[i]) ++chosen;
	if (chosen != 2 * N) return void (puts("0"));

	int ans = 1, sum_point = 0;
	for (int i = 1; i <= 2 * N; ++i)
		if (!Vis[i])
		{
			int now = Process (i);
			ans = (LL) ans * now % Mod * merge (sum_point, tree[0]) % Mod;
			sum_point += tree[0];
		}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= 2 * N; ++i) 
	{
		int x = read<int>(), y = read<int>();
		Choose[x] = Choose[y + N] = 1;
		add_edge (x, y + N, x + y);
		add_edge (y + N, x, x + y);
	}
}

int main()
{

#ifdef hk_cnyali
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	MATH :: init ();
	Input ();
	Solve ();

	return 0;
}