Submission #2208056

---

Source Code Expand

#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

void Get_Val(int &Ret)
{
	Ret = 0;
	char ch;
	while (ch = getchar(), ch > '9' || ch < '0')
		;
	do
	{
		(Ret *= 10) += ch - '0';
	}
	while (ch = getchar(), ch >= '0' && ch <= '9');
}

const int Max_N(200050);
typedef long long int LL;
const int MOD(1000000000 + 7);

inline int Mult(const int &a, const int &b)
{
	return (a * 1LL) * b % MOD;
}

void exgcd(const int &a, const int &b, int &x, int &y)
{
	if (b == 0)
		x = 1, y = 0;
	else
		exgcd(b, a % b, y, x), y -= x * (a / b);
}

inline int inverse(const int &a)
{
	int invx, invy;
	exgcd(a, MOD, invx, invy);
	return (invx % MOD + MOD) % MOD;
}

struct node
{
	node(const int &_pos = 0, const int &_w = 0) : pos(_pos), w(_w) {}
	int pos, w;
};
int N, X, Y, Father[Max_N], Fac[Max_N], Inv[Max_N];
map<int, int> S[Max_N];
vector<node> V[Max_N];

int Get_Father(const int &x)
{
	return Father[x] == x ? x : Father[x] = Get_Father(Father[x]);
}

inline void Link(const int &u, const int &v)
{
	Father[Get_Father(u)] = Get_Father(v);
}

inline bool comp(const node &a, const node &b)
{
	return a.w < b.w;
}

void init()
{
	Get_Val(N), Get_Val(X), Get_Val(Y);
	for (int i = 1, c, w;i <= N;++i)
		Father[i] = i, Get_Val(c), Get_Val(w), V[c].push_back(node(i, w));
	for (int c = 1;c <= N;++c)
		sort(V[c].begin(), V[c].end(), comp);
	Fac[0] = 1;
	for (int i = 1;i <= N;++i)
		Fac[i] = Mult(Fac[i - 1], i);
	Inv[N] = inverse(Fac[N]);
	for (int i = N - 1;i >= 0;--i)
		Inv[i] = Mult(Inv[i + 1], i + 1);
}

//把每个球当做一个点，某个球当前所在的位置是该点的权值。我们将能够交换位置的两个球之间连一条边，那么有边的两个点之间可以交换权值
//考虑两个都在同一个联通块中的点1和n，他们之间的路径是1, 2, 3, ..., n
//可以形如1, 2, 3, ..., n  ->  2, 3, ..., n, 1  ->  n, 2, 3, ..., 1的方式交换，来做到交换两个点的权值而不影响其它点的权值
//可以只考虑联通块中W最小的点来优化连边
//最后每个联通块都是独立的，可以分开做 
void makegraph()
{
	for (int c = 1;c <= N;++c)
		for (int i = 1;i < V[c].size();++i)
			if (V[c][i].w + V[c][0].w <= X)
				Link(V[c][i].pos, V[c][0].pos);
	int Minpos(-1), Minw, Minc;
	for (int c = 1;c <= N;++c)
		for (int i = 0;i < V[c].size();++i)
			if (Minpos == -1 || V[c][i].w < Minw)
				Minpos = V[c][i].pos, Minw = V[c][i].w, Minc = c;
	for (int c = 1;c <= N;++c)
		if (c != Minc)
			for (int i = 0;i < V[c].size();++i)
				if (V[c][i].w + Minw <= Y)
					Link(V[c][i].pos, Minpos);
	Minpos = -1;
	for (int c = 1;c <= N;++c)
		if (c != Minc)
			for (int i = 0;i < V[c].size();++i)
				if (Minpos == -1 || V[c][i].w < Minw)
					Minpos = V[c][i].pos, Minw = V[c][i].w;
	if (Minpos == -1)
		return;
	for (int i = 0;i < V[Minc].size();++i)
		if (V[Minc][i].w + Minw <= Y)
			Link(V[Minc][i].pos, Minpos);
	
}

int js(const int &pos)
{
	int Sum(0), Ans(1);
	for (map<int, int>::iterator it = S[pos].begin();it != S[pos].end();++it)
		Ans = Mult(Ans, Inv[it -> second]), Sum += it -> second;
	return Mult(Ans, Fac[Sum]);
}

void work()
{
	for (int c = 1;c <= N;++c)
		for (int i = 0;i < V[c].size();++i)
			++S[Get_Father(V[c][i].pos)][c];
	int Ans(1);
	for (int i = 1;i <= N;++i)
		if (S[i].size())
			Ans = Mult(Ans, js(i));
	printf("%d", Ans);
}

int main()
{
	init();
	makegraph();
	work();
	return 0;
}

Submission Info

Judge Result