不错的题。bx Ender32k。
我们发现交换有传递性,那么我们能交换就连边,答案是 \(\prod \frac{(sz)!}{\prod c_i!}\),其中 \(sz\) 为连通块大小,\(c_i\) 为这个连通块中第 \(i\) 种颜色出现次数。于是我们得到了一个 \(O(n^2)\) 的做法。
发现很多遍是无用的,考虑舍弃无用边。对于第一种连边,我们只与这种颜色的最小值的点连边;对于第二种连边,我们只与最小值最小和次小的点连边。然后就做完了。
code
// Problem: D - Colorful Balls
// Contest: AtCoder - AtCoder Grand Contest 012
// URL: https://atcoder.jp/contests/agc012/tasks/agc012_d
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 200100;
const int N = 200000;
const ll mod = 1000000007;
const int inf = 0x3f3f3f3f;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
int n, X, Y, a[maxn], b[maxn], p[maxn], stk[maxn], top, m, d[maxn];
pii c[maxn];
ll fac[maxn], ifac[maxn], ans = 1;
bool vis[maxn];
vector<int> G[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
inline void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
void dfs(int u) {
vis[u] = 1;
ans = ans * ifac[m] % mod * fac[d[a[u]]] % mod;
++d[a[u]];
++m;
ans = ans * fac[m] % mod * ifac[d[a[u]]] % mod;
stk[++top] = a[u];
for (int v : G[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
void solve() {
scanf("%d%d%d", &n, &X, &Y);
for (int i = 1; i <= n; ++i) {
c[i] = make_pair(inf, -1);
p[i] = i;
}
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i], &b[i]);
c[a[i]] = min(c[a[i]], make_pair(b[i], i));
}
sort(p + 1, p + n + 1, [&](int x, int y) {
return c[x] < c[y];
});
for (int i = 1; i <= n; ++i) {
if (c[a[i]].fst + b[i] > X || c[a[i]].scd == i) {
continue;
}
G[i].pb(c[a[i]].scd);
G[c[a[i]].scd].pb(i);
}
if (n > 1 && c[p[2]].scd != -1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 2; ++j) {
if (a[c[p[j]].scd] != a[i] && b[c[p[j]].scd] + b[i] <= Y) {
G[i].pb(c[p[j]].scd);
G[c[p[j]].scd].pb(i);
}
}
}
}
for (int i = 1; i <= n; ++i) {
if (vis[i]) {
continue;
}
m = 0;
dfs(i);
while (top) {
int x = stk[top--];
d[x] = 0;
}
}
printf("%lld\n", ans);
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Colorful AtCoder Contest Grand Ballscolorful atcoder contest grand authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 001 atcoder contest grand 022 avoidance atcoder contest grand histogram atcoder contest grand atcoder contest grand 019 atcoder contest grand 017