AGC 012 D - Colorful Balls

为什么atcoder都是神仙题啊qwq

首先发现如果要让 x,y 互换位置的话，要么通过他们直接换 (也就是x和y满足两种操作之一)，要么间接换，通过一些其他的元素形如 x可以和 a[1]换，a[1]可以和a[2]换。。。a[k-1]可以和a[k]换，a[k]可以和y换，x就可以和y换啦。

所以就可以建模到一个无向图上，发现一个联通块内的元素之间都是可以随便换的，所以答案就是每个联通分量的颜色序列数的乘积。。

而一个联通分量的颜色序列数是等于 sz!/(col[1]!)(col[2]!)...(col[n]!) ，sz是该联通块的大小。。。

因为很显然这就是可重排列嘛qwq。

但现在最大的问题是我们图的边数还是 O(N^2) 的，直接dfs会gg掉。。。。

现在我们的任务是尽量缩减图的边数但又不影响连通性。

1.连接相同颜色节点的边:

发现都可以向该颜色重量最轻的节点连边，假如 x,y,z 三点颜色相同，w[x]<w[y]<w[z]，那么(y,z)之间有边 => (x,y)有边且(x,z)有边，但反着不一定成立。

2.连接不同颜色节点的边:

设每种颜色最轻的节点为 lt[i] ，那么我们只需要找到最小的两个 lt[i] ，设为 p,q，每个点只需要向p,q连边即可(如果可以连的话)。

发现颜色具体是啥不影响连边，所以设p的颜色是1，q的颜色是2。

让我们假设 (s,t) 之间有边 (weight(s) + weight(y) <= y)，它们的颜色是 S,T (S<T)，那么:

(1) . S==1 且 T==2 , 那么一条可以的路径是 S -> q -> p -> T

(2). S!=1 且 T!=1 ，那么一条可以的路径是 S -> p -> T

(3) . S!=2 且 T!=2 , 那么一条可行的路径是 S -> q -> p -> T （要清楚 T永远是>1的）

可以发现上述三种情况的并集是 (S,T) 可以取的全集，所以证明了这么做是对的。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

#define pb push_back

const int ha=1e9+7,N=200005;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}

inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

inline int ksm(int x,int y){

	int an=1;

	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;

	return an;

} 

inline int read(){

	int x=0; char ch=getchar();

	for(;!isdigit(ch);ch=getchar());

	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';

	return x;

}

vector<int> g[N],now;

int dfn[N],dc,num[N],jc[N],ni[N],ans=1,sz;

int n,X,Y,col[N],w[N],mn[N],p[N],pos[2],C;

bool v[N];

inline void ae(int x,int y){ g[x].pb(y),g[y].pb(x);}

inline void init(){

	// prepare n! and (n!)^(-1)

	jc[0]=1;

	for(int i=1;i<=n;i++) jc[i]=jc[i-1]*(ll)i%ha;

	ni[n]=ksm(jc[n],ha-2);

	for(int i=n;i;i--) ni[i-1]=ni[i]*(ll)i%ha;

	// prepare edges between different colors

	for(int i=1;i<=n;i++)

	    if(mn[i]<mn[pos[0]]) pos[1]=pos[0],pos[0]=i;

		else if(mn[i]<mn[pos[1]]) pos[1]=i;

	pos[0]=p[pos[0]],pos[1]=p[pos[1]];

	int yz=Y-w[pos[0]],yo=Y-w[pos[1]],cx=col[pos[0]],cy=col[pos[1]];

	for(int i=1;i<=n;i++){

		C=col[i];

		if(C!=cx&&w[i]<=yz) ae(i,pos[0]);

		if(C!=cy&&w[i]<=yo) ae(i,pos[1]);

	}

	// prepare edges between the same colors

	for(int i=1;i<=n;i++){

		C=col[i];

	    if(i!=p[C]&&w[i]+w[p[C]]<=X) ae(i,p[C]);

	}

}

void dfs(int x){

	v[x]=1,sz++,C=col[x];

	if(dfn[C]!=dc) dfn[C]=dc,now.pb(C),num[C]=1;

	else num[C]++;

	for(int i:g[x]) if(!v[i]) dfs(i);

}

inline void solve(){

	// calculate

	for(int i=1;i<=n;i++) if(!v[i]){

		dc++,now.clear(),sz=0;

		dfs(i),ans=ans*(ll)jc[sz]%ha;

		for(int j:now) ans=ans*(ll)ni[num[j]]%ha;

	}

}

int main(){

	memset(mn,0x3f,sizeof(mn)),w[0]=1e9+233;

	n=read(),X=read(),Y=read();

	for(int i=1;i<=n;i++){

		C=col[i]=read(),w[i]=read();

		if(w[i]<mn[C]) mn[C]=w[i],p[C]=i;

	}

	init(),solve();

	printf("%d\n",ans);

	return 0;

}

巴特西

AGC 012 D - Colorful Balls

最新文章

热门文章