A - 资本家 kal0rona

我们可以考虑把每个员工的前缀收益放在折线图上进行考虑：一条折线从$(1, 0)$出发，在$(x, y)$向上走就是给第$x$个员工发钱，上升高度就是发钱数量。最后，把老板当作第$n + 1$个员工即可。可以发现，因为这个是前缀收益，所以最后我们会走到$(n + 1, m)$，我们只需要算从$(1, 0)$到$(n + 1, m)$的不降路径数即可，也就是${n + m \choose m}$。

对于前 40% 的分我们只需要暴力处理组合数即可，用递推式：${n \choose k} = {n - 1 \choose k} + {n - 1 \choose k - 1}$即可。那么对于前 60% 的分我们需要用 Lucas 定理进行处理，也就是：
$$
{n \choose k} \bmod p = {\lfloor \frac{n}{p} \rfloor \choose \lfloor \frac{k}{p} \rfloor} \cdot {n \bmod p \choose k \bmod p} \bmod p
$$
发现 $p$ 很小，我们就可以直接处理 $p$ 以内的阶乘和逆元即可计算。

那么对于 80% 的分数，我们可以对不同的模数做两次，然后用 CRT 进行合并即可。那么对于全部分数，就需要一点技巧。我们仍然使用 CRT 进行合并，但是对于每一个质数幂来说计算方式有变化：

我们发现质数幂不能用正常的 Fermat Little Therom 来算，因为有些数字是没有逆元的。在模$p^c$意义下，如果$\gcd(x, p^c) \neq 1$，那么这样的$x$是没有逆元的。那我们如何来计算呢？首先，我们先把组合数写出来：
$$
{n \choose k} \bmod p^c = \frac{n!}{(n - k)!k!} \bmod p^c = p^x \frac{f(n!)}{f[(n - k)!]f(k!)} \bmod p^c
$$
其中，我们可以把阶乘中的$p$的幂给提取出来，然后进行上下化简。对于分母，由于与$p$互质，所以可以直接用扩展欧几里得算法得出逆元。至于$p^x$，可以直接快速幂。然后上下式可以直接用类似 Lucas 定理的方式处理（在模意义下，阶乘是有循环率的，自己打个表康康即可）即可。处理时需要记录$p$的出现次数。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, m, p, primes[MAX_N], cnt[MAX_N], ptot, cmod, pic[MAX_N], ai[MAX_N];

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y), t = x;
    x = y, y = t - (a / b) * y;
    return d;
}

int getInv(int a)
{
    int x, y;
    exgcd(a, cmod, x, y);
    return (x + cmod) % cmod;
}

int quick_pow(int bas, int tim)
{
    if (tim < 0)
        return quick_pow(getInv(bas), -tim);
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % cmod;
        bas = 1LL * bas * bas % cmod;
        tim >>= 1;
    }
    return ret;
}

int fac(int x, int mod)
{
    int ret = 1;
    for (int i = 1; i <= x; i++)
        if (i % mod != 0)
            ret = 1LL * ret * i % cmod;
    return ret;
}

int fac(int x, int mod, int &tot)
{
    // lucas;
    if (x < mod)
        return fac(x, mod);
    int seg = x / cmod, rem = x % cmod;
    int res = 1LL * quick_pow(fac(cmod - 1, mod), seg) * fac(rem, mod) % cmod;
    tot += x / mod;
    res = 1LL * res * fac(x / mod, mod, tot) % cmod;
    return res;
}

int binomial(int n_, int k_, int mod)
{
    int a = 0, b = 0, c = 0, res = 1;
    res = 1LL * res * fac(n_, mod, a) % cmod * getInv(fac(k_, mod, b)) % cmod * getInv(fac(n_ - k_, mod, c)) % cmod;
    return 1LL * res * quick_pow(mod, a - (b + c)) % cmod;
}

void factorize(int tmp)
{
    for (int i = 2; 1LL * i * i <= tmp; i++)
        if (tmp % i == 0)
        {
            primes[++ptot] = i;
            while (tmp % i == 0)
                cnt[ptot]++, tmp /= i;
        }
    if (tmp > 1)
        primes[++ptot] = tmp, cnt[ptot] = 1;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p), n += m;
    factorize(p);
    for (int i = 1; i <= ptot; i++)
    {
        cmod = 0x7fffffff, cmod = pic[i] = quick_pow(primes[i], cnt[i]);
        ai[i] = binomial(n, m, primes[i]);
    }
    cmod = 0x7fffffff;
    // begins to merge;
    for (int i = 2; i <= ptot; i++)
    {
        int x, y;
        exgcd(pic[i - 1], pic[i], x, y);
        pic[i] *= pic[i - 1];
        ai[i] = ((1LL * x * (ai[i] - ai[i - 1]) * pic[i - 1] % pic[i] + ai[i - 1]) % pic[i] + pic[i]) % pic[i];
    }
    printf("%d\n", ai[ptot]);
    return 0;
}

B - XOR-MIN-MAX

这道题很适合作为被 A 穿签到题，利用了分治的思想，很适合缺乏分治思维训练的选手。

我们可以设置任务$solve(dep, l, r)$为「确定最大值下标在$[l, r]$，正在处理第$dep$位」。具体如何理解呢？首先，显然高位的权要比低位的权要高，那么，如果这段区间中所有数的第$dep$位并不能被消成$0$，也就是这段区间内的数在第$dep$位存在$0, 1$两种情况，那么在$X_{dep}$中我们选$0, 1$都无法让最大值小于$2^{dep}$，那么我们可以分类讨论：把在$[l, r]$之间，$dep$这一位为$0, 1$的数字分类成集合$A, B$，然后把它们第$dep$位都赋为$1$。

如果$X$的第$dep$位为$0$，则最大值将会出现在集合$B$中，执行$solve(mid + 1, r, dep - 1)$；反过来同理。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, ai[MAX_N], ans = 0x7fffffff, tmp[MAX_N];

void solve(int l, int r, int dep)
{
    if (l > r)
        return;
    if (dep == -1)
    {
        int max_val = 0;
        for (int i = l; i <= r; i++)
            max_val = max(max_val, ai[i]);
        ans = min(ans, max_val);
        return;
    }
    int lptr = l, rptr = r, cnt0 = 0, cnt1 = 0;
    for (int i = l; i <= r; i++)
        if (ai[i] & (1 << dep))
            tmp[rptr--] = ai[i], cnt1++;
        else
            tmp[lptr++] = ai[i], cnt0++;
    if (cnt1 == (r - l + 1))
        for (int i = l; i <= r; i++)
            ai[i] = (tmp[i] ^ (1 << dep));
    else if (cnt0 == (r - l + 1))
        for (int i = l; i <= r; i++)
            ai[i] = tmp[i];
    else
        for (int i = l; i <= r; i++)
            ai[i] = (tmp[i] | (1 << dep));
    solve(l, lptr - 1, dep - 1), solve(lptr, r, dep - 1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]);
    solve(1, n, 29);
    printf("%d\n", ans);
    return 0;
}

C - 平面上的点

$\Theta(n^2)$暴力还是很好写的，先枚举水平线，然后再分上下讨论；讨论中，我们都要从左往右枚举，但是我们有两个指针$lptr, rptr$，我们可以在过程中维护在$[lptr, rptr]$之间的颜色数始终严格小于$k$，然后再用点个数更新答案。

那么正解就没这么好写了。我们考虑在$k$中枚举一个被排除的颜色，然后分情况讨论：

• 按$x$排序，相邻点对做垂直线，两线之间的点个数可能成为答案。
• 向上看，我们可以把点按$y$降序排序，然后让矩形的横线段$[l, r]$强行$\in x_i$，也就是置横线段为当前点之上。用 multiset 查询当前点前驱后继的$x$作为矩形的横线范围，然后把当前点的$y + 1$作为基准线，用主席树查询当前矩形内的点数。
• 向下看类似。

详细见代码：

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 4e5 + 200;

int T, n, k, roots[MAX_N], yupper, gans;

struct point
{
    int x, y, c;
    bool operator<(const point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
} pts[MAX_N];

typedef multiset<point>::iterator mpit;

bool compareByY(const point &rhs1, const point &rhs2) { return rhs1.y < rhs2.y || (rhs1.y == rhs2.y && rhs1.x < rhs2.x); }

vector<point> ptByColor[MAX_N];
vector<int> mpx, mpy;

inline char nc()
{
    static char buf[10000000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 10000000, stdin), p1 == p2) ? EOF : *p1++;
}

int read()
{
    int x = 0, f = 1;
    char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + ch - '0', ch = nc();
    return x * f;
}

namespace PST
{

struct node
{
    int lson, rson, val;
} nodes[MAX_N << 5];

int ptot;

int update(int qx, int l, int r, int pre)
{
    int p = ++ptot;
    nodes[p] = nodes[pre], nodes[p].val++;
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    if (qx <= mid)
        nodes[p].lson = update(qx, l, mid, nodes[pre].lson);
    else
        nodes[p].rson = update(qx, mid + 1, r, nodes[pre].rson);
    return p;
}

int query(int ql, int qr, int l, int r, int pre, int p)
{
    if (ql > qr)
        return 0;
    if (ql <= l && r <= qr)
        return nodes[p].val - nodes[pre].val;
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid)
        ret += query(ql, qr, l, mid, nodes[pre].lson, nodes[p].lson);
    if (mid < qr)
        ret += query(ql, qr, mid + 1, r, nodes[pre].rson, nodes[p].rson);
    return ret;
}

void init()
{
    ptot = 0;
    int last_ptr = 0;
    for (int i = 1, r = 0; i <= n; i = r + 1)
    {
        r = i, roots[pts[i].x] = update(pts[i].y, 1, yupper, last_ptr), last_ptr = roots[pts[i].x];
        while (r + 1 <= n && pts[r + 1].x == pts[i].x)
            r++, roots[pts[i].x] = update(pts[r].y, 1, yupper, last_ptr), last_ptr = roots[pts[i].x];
    }
}

} // namespace PST

int ripe(vector<int> &vec, int x) { return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1; }

void processCategory(int color)
{
    using namespace PST;
    if (ptByColor[color].empty())
        return (void)(gans = max(gans, n));
    sort(ptByColor[color].begin(), ptByColor[color].end());
    // horizontal intervals;
    gans = max(gans, query(1, yupper, 1, yupper, 0, roots[ptByColor[color].front().x - 1]));
    for (int i = 1, siz = ptByColor[color].size(); i < siz; i++)
    {
        point pt = ptByColor[color][i];
        gans = max(gans, query(1, yupper, 1, yupper, roots[ptByColor[color][i - 1].x], roots[pt.x - 1]));
        continue;
    }
    gans = max(gans, query(1, yupper, 1, yupper, roots[ptByColor[color].back().x], roots[mpx.size()]));
    // looking up;
    sort(ptByColor[color].begin(), ptByColor[color].end(), compareByY);
    multiset<point> ms;
    for (int siz = ptByColor[color].size(), i = siz - 1; i >= 0; i--)
    {
        mpit curt = ms.insert(ptByColor[color][i]);
        int baseLine = ptByColor[color][i].y + 1;
        int l, r;
        if (curt != ms.begin())
            curt--, l = curt->x, curt++;
        else
            l = 0;
        curt++;
        if (curt != ms.end())
            r = curt->x - 1;
        else
            r = mpx.size();
        curt--;
        gans = max(gans, query(baseLine, yupper, 1, yupper, roots[l], roots[r]));
    }
    ms.clear();
        // looking down;
    for (int siz = ptByColor[color].size(), i = 0; i < siz; i++)
    {
        mpit curt = ms.insert(ptByColor[color][i]);
        int baseLine = ptByColor[color][i].y - 1;
        int l, r;
        if (curt != ms.begin())
            curt--, l = curt->x, curt++;
        else
            l = 0;
        curt++;
        if (curt != ms.end())
            r = curt->x - 1;
        else
            r = mpx.size();
        curt--;
        gans = max(gans, query(1, baseLine, 1, yupper, roots[l], roots[r]));
    }
}

int main()
{
    T = read();
    while (T--)
    {
        n = read(), k = read();
        mpx.clear(), mpy.clear(), gans = 0;
        for (int i = 1; i <= n; i++)
        {
            pts[i].x = read(), pts[i].y = read(), pts[i].c = read();
            mpx.push_back(pts[i].x), mpy.push_back(pts[i].y);
        }
        sort(mpx.begin(), mpx.end()), mpx.erase(unique(mpx.begin(), mpx.end()), mpx.end());
        sort(mpy.begin(), mpy.end()), mpy.erase(unique(mpy.begin(), mpy.end()), mpy.end());
        yupper = mpy.size();
        for (int i = 1; i <= k; i++)
            ptByColor[i].clear();
        for (int i = 1; i <= n; i++)
        {
            pts[i].x = ripe(mpx, pts[i].x), pts[i].y = ripe(mpy, pts[i].y);
            ptByColor[pts[i].c].push_back(pts[i]);
        }
        sort(pts + 1, pts + 1 + n), PST::init();
        for (int i = 1; i <= k; i++)
            processCategory(i);
        printf("%d\n", gans);
    }
    return 0;
}