首先用 \(2n\) 个点表示每个机器人,原图中的一个球转化为图上的一条边,于是转化为一个二分图模型。
我们对这个二分图的每个连通块分开考虑(假设有 \(cnt\) 个连通块),显然一个大小为 \(s\) 的连通块应该有 \(s\) 条边,于是这既是一个二分图也是一个基环树。
二分图+基环树唯一的性质应该就是基环树中间的那个环是偶环,但这个性质在这题没什么用。
考虑先选出每个球是被哪个机器人消灭的,这就相当于一个边定向问题。我们为这个图上面的每一条边定向,边指向的点表示这条边所代表的球是被那个指向的机器人消灭的。
根据题意每个点的入度只能恰好为 \(1\),于是这棵基环树的定向方案只有两种:挂在环上的链肯定都是往外指的,而环上的边有顺时针或逆时针两种定向方案。
那么我们对两种定向方案都枚举一遍,于是假设当前的定向方案已经确定了。那么我们就是要考虑合法选边顺序的总方案数。
这里 “合法” 的要求是指:假设有一条边 \(x\to y'\),意思是用第 \(y'\) 列的机器人去消 \((x,y')\) 这个球,那么显然你需要保证满足横坐标 \(t\in[1,x)\) 的所有点 \((t,y')\) 都已经被消灭。那么我们让 \(y'\) 向所有 \(t\in[1,x)\) 连边,表示当前定向方案中要使用机器人 \(y'\) 必须先使用机器人 \(t\)。
显然这样会构成若干个外向 DAG,更具体地,由于每个点至多只有 \(1\) 的入度,所以这是若干棵外向树。
那么合法的选边顺序就相当于这个图(为若干棵树)中合法的拓扑序个数,而对于一棵大小为 \(n'\) 的树来说它的拓扑序个数为 \(\dfrac{n'!}{\prod_u sz_u}\)。
引理:一棵大小为 \(n\) 的树的拓扑序个数为 \(\dfrac{n!}{\prod_{u}sz_u}\)。
证明:先考虑 DP,设 \(f_u\) 表示以 \(u\) 为根的子树的拓扑序个数。
求 \(f_u\) 时,注意到 \(u\) 的每个儿子 \(v\) 的子树是互不影响的,所以我们考虑先确定每棵 \(v\) 子树在拓扑序中所占的位置,再考虑对于每棵 \(v\) 子树,把这棵子树所包含的点分配到这棵子树所占的位置。后面 \(v\) 子树内的点的分配位置的方案数就是 \(f_v\),而前面为所有子树分配位置相当于一个可重集排列,于是有:
\[f_u=\dfrac{(sz_u-1)!}{\prod_{v}sz_v!}\prod_v f_v \]不断代入即可得到引理的式子。
那么现在有 \(cnt\) 个连通块每个连通块都有多棵树怎么办呢?我们可以用一个虚点把所有的树根连起来变成一个新的大树,直接求这棵大树的拓扑序个数即可。
那么我们就需要求出每种定向方案的 \(\prod_usz_u\) 的和,显然由于连通块之间互不影响,我们并不需要 \(O(2^{cnt})\) 枚举所有的定向方案,只需要对每个连通块把它的两种定向方案的 \(\prod_{u}sz_u\) 加起来,再把每个连通块乘起来即可。
代码如下:
#include<bits/stdc++.h>
#define N 200010
using namespace std;
namespace modular
{
const int mod=1000000007;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
}using namespace modular;
inline int poww(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,fac[N];
int ne,S,PRE;
int cnt,head[N],to[N<<1],nxt[N<<1];
int du[N],pre[N],size[N];
bool vis[N];
vector<int>p;
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void findring(int u,int fa)
{
p.push_back(u);
vis[u]=1;
for(int i=head[u];i;i=nxt[i])
{
ne++;
int v=to[i];
if(v==fa) continue;
if(vis[v])
{
PRE=u,S=v;
continue;
}
findring(v,u);
}
}
void Direc(int u)
{
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(pre[v]||v==pre[u]) continue;
pre[v]=u;
Direc(v);
}
}
int calc(int u)
{
size[u]=1;
int prod=1;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v<pre[u])
{
prod=mul(prod,calc(v));
size[u]+=size[v];
}
}
return mul(prod,size[u]);
}
int solve()
{
for(int u:p) pre[u]=du[u]=0;
pre[S]=PRE;
Direc(S);
for(int u:p)
{
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v<pre[u]) du[v]++;
}
}
int res=1;
for(int u:p)
if(!du[u])
res=mul(res,calc(u));
return poww(res,mod-2);
}
int main()
{
n=read();
fac[0]=1;
for(int i=1;i<=(n<<1);i++)
fac[i]=mul(fac[i-1],i);
for(int i=1;i<=(n<<1);i++)
{
int x=read(),y=read();
adde(x,n+y),adde(n+y,x);
}
int ans=fac[n<<1];
for(int i=1;i<=(n<<1);i++)
{
if(!vis[i])
{
p.clear(),ne=0;
findring(i,0);
if(ne/2!=(int)p.size())
{
puts("0");
return 0;
}
int s1=solve();
swap(S,PRE);
int s2=solve();
ans=mul(ans,add(s1,s2));
}
}
printf("%d\n",ans);
return 0;
}
标签:Collecting,连通,Balls,int,拓扑,ARC083F,基环树,prod,定向
From: https://www.cnblogs.com/ez-lcw/p/16837095.html