[??记录]AT3537 [ARC083D] Collecting Balls
command_block
2021-05-09 12:57:34
**题意** ： 在平面直角坐标系上有 $2n$ 个小球，第 $i$ 个小球在 $x_i,y_i$ ，满足 $x_i,y_i\in[1,n]∩Z$。
有 $n$ 个 A 类机器人，第 $i$ 个在 $(0,i)$ ，有 $n$ 个 B 类机器人，第 $i$ 个在 $(i,0)$ 。
启动一个 A 类机器人后，它会向右走，将碰到的第一个球收集起来，并消失。
启动一个 B 类机器人后，它会向上走，将碰到的第一个球收集起来，并消失。
只有上一个机器人返回起点后，下一个机器人才会被启动。
求有多少种启动机器人的顺序，能够收集完所有小球。方案数对$10^9+7$取模 。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
## **Part1**
记第 $i$ 个 A 类机器人为 $A_i$ ，第 $i$ 个 B 类机器人为 $B_i$。
对于球 $(x,y)$ ，它可以被机器人 $A_y$ 或者 $B_x$ 清除。
考虑建立图论模型，连边 $(A_y,B_x)$。对于每条边，必须选择一个端点来将其收集。
不难发现，若某个连通块中 点数 $<$ 边数 ，则无解。又因为本题中 总点数 $=$ 总边数，故图一定是基环树森林。
我们将每条边定向，指向用于收集它的点。不难发现，唯一的方案是定成**基环外向树**，这样每个点的入度都为 $1$。
## **Part2**
在确定了机器人和球的匹配的基础上，考虑如何处理“机器人每次只会拿最近的球”的约束。
若 $A_i$ 要收集球 $(x,i)$ ，则对于满足 $x'<x$ 的其他球 $(x',i)$ ，必须先收集。
（此时，$x'\neq x$ 的其他球 $(x',i)$ 必然由 B 类机器人收集）
对于 $B$ 也有类似的约束。
若机器人 $u$ 必须先于 $v$ 行动，则连边 $u\rightarrow v$ ，合法排列数即为该有向图的合法拓扑序数。
观察该有向图的性质 ：
- 每个点只会向右或向上连边，故该图为 $\rm DAG$。
- 对于某个 B 类机器人，只可能向至多一个 A 类机器人连边。A 类机器人类似。
故每个点只有至多一个出边，图为**内向树森林**。
对内向树森林求拓扑序数目是经典问题。
记森林总点数为 $n$ ，节点 $u$ 的子树大小为 $siz_u$ ，则拓扑序数目为 ：
$$\dfrac{n!}{\prod_{i=1}^nsiz_i}$$
- **证明** ： 注意到，森林等价于将所有树连到一个新点上形成的树。
对于节点 $u$ ，设儿子分别为 $v_1,v_2,...,v_m$。记点 $u$ 子树内的拓扑序数目为 $f_u$。
将 $u$ 删除，看做森林。利用多重排列归并儿子的拓扑序，则 ：
$$f_u=\dfrac{(siz_u-1)!}{\prod_{i=1}^msiz_{v_i}!}\prod_{i=1}^mf_{v_i}$$
利用上式归纳，假设 $v_{1...m}$ 的子树内都满足结论 ：
$$
\begin{aligned}
f_u&=\dfrac{(siz_u-1)!}{\prod_{i=1}^msiz_{v_i}!}\prod_{i=1}^m\dfrac{siz_{v_i}!}{\prod_{t\text{在}v_i\text{的子树内}}siz_t}\\
&=\dfrac{(siz_u-1)!}{\prod_{i=1}^m\prod_{t\text{在}v_i\text{的子树内}}siz_t}\\
&=\dfrac{siz_u!}{\prod_{t\text{在}u\text{的子树内}}siz_t}
\end{aligned}
$$
于是证毕。
## **Part3**
接下来考虑，对于多种机器人和球之间的匹配，如何求答案的和。
Part1 中发现，生成匹配的图为基环树森林，我们对每棵基环树分别处理，最后用多重排列归并。
对于某棵基环树，将其变为基环内向树的方案数总有两种，因为环有两种方向。
对这两种匹配分别用 Part2 中的算法求解合法排列数即可。
复杂度为 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define MaxN 200500
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN],inv[MaxN];
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
for (int i=1;i<=n;i++)
inv[i]=ifac[i]*fac[i-1]%mod;
}
struct UFS{
int f[MaxN];bool vis[MaxN];
void Init(int n)
{for (int i=1;i<=n;i++)f[i]=i;}
int find(int u)
{return f[u]==u ? u : f[u]=find(f[u]);}
bool merge(int u,int v){
u=find(u);v=find(v);
if (u==v)return 0;
f[u]=v;return 1;
}
}T;
vector<int> g[MaxN],id[MaxN];
void adl(int u,int v,int p){
g[u].pb(v);id[u].pb(p);
g[v].pb(u);id[v].pb(p);
}
bool vis[MaxN],fl[MaxN];
int n,f[MaxN],tn,st[MaxN],tn2,st2[MaxN];
void dfs1(int u,int fa)
{
f[u]=fa;
for (int i=0;i<g[u].size();i++)
if (g[u][i]!=fa){
st2[++tn2]=id[u][i];
dfs1(g[u][i],u);
}
}
void dfs2(int u)
{
vis[u]=1;
for (int i=0,v;i<g[u].size();i++)
if (!vis[v=g[u][i]]){
fl[id[u][i]]=v>n;
dfs2(v);
}
}
vector<int> g2[MaxN];
int in[MaxN];
int siz[MaxN];
void dfs3(int u)
{
siz[u]=1;
for (int i=0;i<g2[u].size();i++){
dfs3(g2[u][i]);
siz[u]+=siz[g2[u][i]];
}
}
struct Line{int u,v;bool fl;}l[MaxN];
void adl2(int u,int v){g2[v].pb(u);in[u]++;}
ll calc()
{
for (int i=1;i<=tn2;i++){
int u=st2[i];
if (fl[u]){
int v=l[u].v;
for (int j=0;j<g[v].size();j++)
if (g[v][j]<l[u].u)
adl2(id[v][j],u);
}else {
int v=l[u].u;
for (int j=0;j<g[v].size();j++)
if (g[v][j]<l[u].v)
adl2(id[v][j],u);
}
}
for (int i=1;i<=tn2;i++)
if (!in[st2[i]])dfs3(st2[i]);
ll ans=fac[tn2];
for (int i=1;i<=tn2;i++){
ans=ans*inv[siz[st2[i]]]%mod;
g2[st2[i]].clear();in[st2[i]]=0;
}return ans;
}
int main()
{
scanf("%d",&n);
T.Init(n+n);Init(n+n);
ll ans=1;
for (int k=1;k<=n+n;k++){
scanf("%d%d",&l[k].u,&l[k].v);l[k].v+=n;
if (T.merge(l[k].u,l[k].v))
adl(l[k].u,l[k].v,k);
else {
int t=T.find(l[k].u);
if (T.vis[t]){puts("0");return 0;}
else l[k].fl=T.vis[t]=1;
}
}
for (int k=1;k<=n+n;k++)
if (l[k].fl==1){
tn=tn2=0;dfs1(l[k].u,0);
for (int p=l[k].v;p;p=f[p])st[++tn]=p;
adl(l[k].u,l[k].v,k);st2[++tn2]=k;
for (int i=1;i<=tn;i++)vis[st[i]]=1;
for (int i=1;i<=tn;i++)dfs2(st[i]);
for (int i=1;i<=tn;i++){
int u=st[i];
for (int j=0;j<g[u].size();j++)
if (g[u][j]==(i==tn ? st[1] : st[i+1]))
fl[id[u][j]]=u>n;
}
ll sav=calc();
for (int i=1;i<=tn;i++){
int u=st[i];
for (int j=0;j<g[u].size();j++)
if (g[u][j]==(i==1 ? st[tn] : st[i-1]))
fl[id[u][j]]=u>n;
}
sav=(sav+calc())%mod;
ans=ans*sav%mod*ifac[tn2]%mod;
}
printf("%lld",ans*fac[n+n]%mod);
return 0;
}
```