crazy_cloud's Blog
0%

ARC083-F Collecting Balls

Posted on Edited on In

题目大意

在二维平面上有 \(2n\) 个球。

在 \((0,i)(1\leq i\leq n)\) 有 \(n\) 个机器人，激活后会拿走纵坐标为 \(i\) 的最左边的球；类似地，在 \((i,0)(1\leq i\leq n)\) 有 \(n\) 个机器人，激活后会拿走横坐标为 \(i\) 的最下面的球。

问一共 \((2n)!\) 种激活顺序中，多少种能拿走所有的球。

\(2\leq n\leq10^5,1\leq x_i,y_i\leq n\)

题目分析

首先有一个这样的思路：我们先确定每个球与机器人之间的匹配关系，然后再利用匹配关系确定激活顺序的一些限制（一定是一个 DAG），然后统计拓扑序的个数。

我们把机器人看成点，球看成边，这样就可以得到一个 \(2n\) 个点 \(2n\) 条边的二分图，然后我们希望能够确定点和边之间的匹配关系。

可以发现，任意一个连通块如果有解点数一定等于边数，也就是一定是一个环套树结构。那么树边显然唯一匹配，环上只有两种匹配。

确定了匹配关系之后，构造激活顺序的 DAG 也很简单，考虑一个条边 \((u,v)\)，如果它与点 \(v\) 匹配，那么 \(v\) 就要先于与其相连的小于 \(u\) 的点被激活，直接连边就好了。

可以发现这样连边得到的图肯定是没有环的，也就是一个有向的森林，接下来就是一个简单的 dp 了。

时间复杂度 \(O(n)\)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int P=1000000007;
const int N=100005;
const int V=N<<1;
const int E=V<<1;

int last[V],last_[V],nxt_[V],tov_[V],vis[V],fact[V],invf[V],X[V],Y[V],cir[V],eid[V],f[V],size[V],deg[V];
int nxt[E],tov[E],bel[E];
bool mark[E];
vector<int> con;
queue<int> q;
int n,v,tot,tot_,tim,ans,ecnt,sizcnt;

inline void insert(int x,int y){++deg[tov[++tot]=y],nxt[tot]=last[x],last[x]=tot;}
inline void insert_(int x,int y){++deg[tov_[++tot_]=y],nxt_[tot_]=last_[x],last_[x]=tot_;}

int quick_power(int x,int y)
{
	int ret=1;
	for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ret=1ll*ret*x%P;
	return ret;
}

void pre()
{
	fact[0]=1;
	for (int i=1;i<=v;++i) fact[i]=1ll*fact[i-1]*i%P;
	invf[v]=quick_power(fact[v],P-2);
	for (int i=v;i>=1;--i) invf[i-1]=1ll*invf[i]*i%P;
}

void dfs(int x)
{
	vis[x]=++tim,con.push_back(x);
	for (int i=last[x],y;i;i=nxt[i])
		if (!mark[i+1>>1]) if (++ecnt,mark[i+1>>1]=1,!vis[y=tov[i]]) dfs(y);
}

inline int C(int n,int m){return 1ll*fact[n]*invf[m]%P*invf[n-m]%P;}

inline int calc()
{
	for (;tot_;tov_[tot_]=nxt_[tot_]=0,--tot_);
	for (int x:con) last_[x]=0;
	for (int x:con)
	{
		int u=size[x]=0;f[x]=1;
		for (int i=last[x];!u&&i;i=nxt[i]) if (bel[i+1>>1]==x) u=tov[i];
		for (int i=last[x];i;i=nxt[i]) if (tov[i]<u) insert_(tov[i],x);
	}
	for (int x:con) if (!deg[x]) q.push(x);
	int ret=1,siz=0;
	for (int x;!q.empty();q.pop())
	{
		++size[x=q.front()];
		bool found=0;
		for (int i=last_[x],y;i;i=nxt_[i])
		{
			if (!--deg[y=tov_[i]]) q.push(y);
			f[y]=1ll*f[y]*f[x]%P*C(size[y]+=size[x],size[x])%P,found=1;
		}
		if (!found) ret=1ll*ret*f[x]%P*C(siz+=size[x],size[x])%P;
	}
	return ret;
}

inline void solve()
{
	if (ecnt!=(int)con.size())
	{
		ans=0;
		return;
	}
	for (int x:con) if (deg[x]==1) q.push(x);
	for (;!q.empty();q.pop())
	{
		int x=q.front();
		for (int i=last[x],y;i;i=nxt[i])
			if (deg[y=tov[i]]-1)
			{
				bel[i+1>>1]=x;
				if (--deg[y]==1) q.push(y);
			}
	}
	int src=0;
	for (int x:con)
		if (deg[x]-1)
		{
			if (!src) src=x;
			vis[x]=0;
		}
	cir[0]=0;
	for (int x=src,y,tar,i,lste=0,i_;!vis[x];vis[cir[++cir[0]]=x]=tim,eid[cir[0]]=lste=i_+1>>1,x=tar)
		for (i=last[x],tar=0;!tar&&i;i=nxt[i])
			if (lste!=i+1>>1&&deg[y=tov[i]]-1) tar=y,i_=i;
	for (int x:con) deg[x]=0;
	cir[cir[0]+1]=cir[1];
	for (int i=1;i<=cir[0];++i) bel[eid[i]]=cir[i];
	int ret=calc();
	for (int i=1;i<=cir[0];++i) bel[eid[i]]=cir[i+1];
	(ret+=calc())%=P;
	ans=1ll*ans*ret%P*C(sizcnt+=ecnt,ecnt)%P;
	con.clear(),ecnt=0;
}

int main()
{
	freopen("balls.in","r",stdin),freopen("balls.out","w",stdout);
	n=read(),v=n<<1;
	for (int i=1;i<=v;++i) X[i]=read(),Y[i]=read(),insert(X[i],Y[i]+n),insert(Y[i]+n,X[i]);
	pre(),ans=1;
	for (int x=1;ans&&x<=v;++x)
		if (!vis[x]) ++tim,dfs(x),solve();
	printf("%d\n",ans);
	fclose(stdin),fclose(stdout);
	return 0;
}