20230922 比赛总结

反思

A

考场降智，没想到拆分成 $2^{\alpha }{5}^{\beta }x$ 的形式，一直在卡精度（thx anti)

B

又是随机题，又是 $bl$ 题，差点又被区分了

C

我是 $sb$，排序顺序有点小问题 $+$ 没判 $-1$（没判 $-1$ 小样例都过不了，本来想后面补的，结果忘了/fk）

题解

D

把行编号为 $1-n$，把列编号为 $n+1-2n$
考虑将有小球的位置 $(x,y)$，把行和列连边，即 $x$ 与 $y+n$ 连边

考虑每一个小球一定会匹配行或列，那么我们如果把 $x\to y+n$ 连边表示 $(x,y)$ 的小球选第 $x$ 行，反之同理
考虑这样一定会形成内向基环树森林，因为每个行或列只会匹配一个
考虑忽略我们自行添加的有向的条件，变成无向
那么指定方向的方案数只有 $2$ 种，即环的方向
现在需要计算当前方案的启动顺序

考虑回到原图中，我们可以把一定在 $x$ 之后启动的点连向它，不难发现，这样的点只有一个，可以画个图理解：

只有这样的情况是需要连边的
这样就会形成森林，然后只要统计树的拓扑序计数即可
简单树形 $dp$ 解决

时间复杂度 $O(n)$，感觉是到典题

#include 
using namespace std;
const int N=200100,P=1e9+7;
int n,fac[N],inv[N];
int e[N<<1],ne[N<<1],h[N],idx;
int circ,depth[N],fa[N],siz[N],f[N];
bool onc[N],ntrt[N];
vector<int> cir,pts,son[N];
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
int C(int a,int b){
    if(a<b||b<0) return 0;
    return 1ll*fac[a]*inv[b]%P*inv[a-b]%P;
}
void dfs1(int u){
	pts.push_back(u);
	depth[u]=depth[fa[u]]+1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==fa[u]) continue;
        if(!depth[v]) fa[v]=u,dfs1(v);
		else if(depth[v]<depth[u]){
			circ++;
			for(int x=u;x!=v;x=fa[x]) cir.push_back(x),onc[x]=1;
			cir.push_back(v),onc[v]=1;
		}
	}
}
void dfs2(int u){
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(!onc[v]&&v!=fa[u]) fa[v]=u,dfs2(v);
	}
}
void dfs3(int u){
	f[u]=1,siz[u]=0;
	for(int v:son[u]){
		dfs3(v);siz[u]+=siz[v];
		f[u]=1ll*f[u]*f[v]%P*C(siz[u],siz[v])%P;
	}
	siz[u]++;
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){
        if(b&1) res=1ll*res*a%P;
        a=1ll*a*a%P;
    }
    return res;
}
int main(){
    freopen("ball.in","r",stdin);
    freopen("ball.out","w",stdout);
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=1ll*fac[i-1]*i%P;
	inv[N-1]=qmi(fac[N-1],P-2);
	for(int i=N-2;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%P;
	n=read();
	memset(h,-1,sizeof(h));
	for(int i=1;i<=n<<1;i++){
		int x=read(),y=read();
		add(x,y+n),add(y+n,x);
	}
	int ans=1,tott=0;
	for(int i=1;i<=n<<1;i++){
		if(depth[i]) continue;
		circ=0;cir.clear(),pts.clear();
		dfs1(i);
		if(circ!=1){ puts("0");exit(0);}
		for(int u:cir) fa[u]=0,dfs2(u);
		int tres=0;
		for(int type=0;type<2;type++){
			if(type){
				for(int i=0;i<cir.size()-1;i++) fa[cir[i]]=cir[i+1];
				fa[cir[cir.size()-1]]=cir[0];
			}
			else{
				for(int i=1;i<cir.size();i++) fa[cir[i]]=cir[i-1];
				fa[cir[0]]=cir[cir.size()-1];
			}
            for(int u:pts) ntrt[u]=0,son[u].clear();
			for(int u:pts) if(fa[fa[u]]>u) ntrt[u]=1,son[fa[u]].push_back(u);//表示fa[u]一定在u后面选择
			int cur=0,res=1;
			for(int u:pts) if(!ntrt[u]){
				dfs3(u);cur+=siz[u];
				res=1ll*res*f[u]%P*C(cur,siz[u])%P;
			}
			tres=(tres+res)%P;
		}
        tott+=pts.size();
		ans=1ll*ans*tres%P*C(tott,pts.size())%P;
	}
	printf("%d\n",ans);
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

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