题解 AT2364 【Colorful Balls】

· · 题解

标签: Luogu 都咩有标签我怎么编的出.

Part 1

我们发现如果球a可以和球b交换且球a可以和球c, 我们可以通过一系列只涉及a,b,c的交换任意决定它们的相对顺序. 经过数学归纳法得, 我们发现相对顺序可以改变的性质是可传递的, 于是可以的到一个十分显然的 \mathcal O(n^2) 的做法:

枚举两个球, 如果满足交换条件就连一条边, 则一个联通块内的所有点可以随意决定相对顺序. 那么我们该如何计算答案呢, 容易发现不同连通块的方案数是独立(分步)的, 所以我们对每个联通快分别求答案然后相乘即可. 易知一个联通快的方案数为\frac{(\sum_i s_i)!}{\prod s_i!}, 其中 s_i 表示第 i 中颜色的点数.

Par2

上述做法还不够优秀, 考虑优化.

发现一个联通块内有许多边是无用的(断开后不影响联通性), 考虑优化这个部分.

发现对于同色相连的边, 只用连重量最小的球和其他球之间的边.

对于异色相连的边, 只用连 最小重量最小的颜色重量最小的球 与 其它颜色的重量最小的球 之间的边 和 最小重量最小的颜色重量非最小的球 与 最小重量次小颜色的重量最小的球之间 的边就好了(有点绕口, 加油! *<|:-) ).

另外, 根据 Part1 可知: 一个联通块内至少有两种颜色对答案才有贡献, 也即如果一种颜色无法与 最小重量最小的颜色 连边, 那么对答案一定没有贡献, 也即只有一个联通块对答案有贡献. 所以图就不用建了, 代码实现非常简单.

复杂度\mathcal O(n).

(由于很简单变量名瞎取).

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int read();
vector<int> c[200005];
int w[200005];

int fsp(int bs, int p) {
    int rt = 1;
    while (p) {
        if (p & 1) rt = 1ll * rt * bs % mod;
        bs = 1ll * bs * bs % mod, p >>= 1;
    }
    return rt;
}

int fac[200005], caf[200005];
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1ll * i * fac[i - 1] % mod;
    caf[n] = fsp(fac[n], mod - 2);
    for (int i = n; i >= 1; --i) caf[i - 1] = 1ll * i * caf[i] % mod;
}

int main() { 
    int n = read(), X = read(), Y = read();
    init(n);
    for (int i = 1, tc, tw; i <= n; ++i) {
        tc = read(), tw = read();
        if (!c[tc].size()) w[tc] = tw;
        c[tc].push_back(tw), w[tc] = min(tw, w[tc]);
    }
    int mc1 = 0, mc2 = 0;
    for (int i = 1; i <= n; ++i) 
        if (c[i].size() && (!mc1 || w[i] < w[mc1])) mc1 = i;
    for (int i = 1; i <= n; ++i) 
        if (c[i].size() && i != mc1 && (!mc2 || w[i] < w[mc2])) mc2 = i;
    if (!mc2 || w[mc1] + w[mc2] > Y) return puts("1"), 0;
    int res1 = 0, res2 = 1;
    for (int i = 1, cnt; i <= n; ++i) {
        if (!c[i].size() || w[i] + w[mc1] > Y) continue;
        cnt = 0;
        for (vector<int>::iterator j = c[i].begin(); j != c[i].end(); ++j) {
            cnt += ((*j) + w[mc1 - i ? mc1 : mc2] <= Y || (*j) + w[i] <= X);
        }
        res1 += cnt, res2 = 1ll * caf[cnt] * res2 % mod;
    }
    printf("%d\n", 1ll * fac[res1] * res2 % mod);
    return 0; 
}

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}