挑战赛 Round 87 题解

A MuQ 的签到题

知识点：位运算、数学、不等式证明、贪心/极值思维

设选出的符卡的最大公因数为 $g$ 。因为这 $m$ 张卡都必须是 $g$ 的倍数，而 $1..n$ 中 $g$ 的倍数最多只有 $⌊n / g⌋$ 个，所以 $m \leq ⌊n / g⌋$ ，从而得到： $mg \leq n$ 。

利用异或与加法的基本性质： $m \oplus g \leq m + g$ ，再由 $(m - 1)(g - 1) \geq 0$ 可得 $m + g \leq mg + 1$ ，结合 $mg \leq n$ ，有：

m \oplus g \leq m + g \leq mg + 1 \leq n + 1

所以答案最多是 $n + 1$ 。

当 $n$ 为偶数：直接选所有的数字，有 $m=n,g=\gcd(1,2,\dots,n) = 1$ ，答案为 $n\oplus 1 = n+1$ 。
当 $n$ 为奇数且 $n>1$ ：选前 $n-1$ （即 $n-1$ 为偶数，选法同上），答案至少为 $(n-1) \oplus 1 = n$ 。接下来证明 $n + 1$ 不可能达到。

若 $m \oplus g = n + 1$ ，由于前面已经有 $m \oplus g \leq m + g \leq mg + 1 \leq n + 1$ ，所以必须每个不等号都取等号。由 $m + g = n + 1,mg = n$ 可知， $m, g$ 只能是一对 $1$ 和 $n$ 。但此时， $1\oplus n = n - 1$ （当 $n$ 为奇数），显然不是 $n + 1$ ，矛盾。

所以 $n + 1$ 无法达到，最大值只能是 $n$ 。
特判当 $n=1$ 时，只能选择 $1$ ，答案为 $1\oplus 1 = 0$ 。

时间复杂度 $O(1)$

void solve() {
    int n;
    cin >> n;
    if (n == 1) cout << 0 << endl;
    else cout << ((n & 1) ? n : n + 1) << endl;
}

B CirnoNine 在梦里的画

知识点：二维前缀和、二维差分、图的连通性判定（BFS / DFS）、二分答案

一个更大的全黑正方形，总能被若干个更小的全黑正方形按路径方式拆出来，原来的合法路径也可以被“细化”成更小方块构成的路径。因此，可行性对 $a$ 是单调的，最大可行值可以二分求出。

Q1：固定一个 $a$ ，怎样判断它是否可行？

如果一个 $a \times a$ 的正方形是全 $1$ ，那么称它的左上角为一个合法位置。对于固定的 $a$ ，我们先找出所有合法位置。设这些合法位置组成的集合为 $S$ 。那么要让 $a$ 可行，必须满足两件事：

$S$ 里的所有位置必须处于同一个四连通块中；
所有合法位置对应的 $a \times a$ 方块并起来，必须恰好覆盖所有黑格（所有 1）。

为什么这样就够了？

如果 $S$ 连通，那么可以在这张“合法位置图”上做一次 $DFS / BFS$ ，构造出一条可以重复走点的路径，依次经过所有合法位置。
每个合法位置对应的 $a \times a$ 方块都全是 $1$ ，而所有黑格又都被这些方块覆盖，那么这些方块的并集就正好是原矩阵中的所有 $1$ 。

所以，固定 $a$ 的判定就变成：判断“所有合法位置是否连通”以及“所有黑格是否都被某个合法位置对应的方块覆盖”。

Q2：如何高效判断固定 $a$ 是否可行？

用二维前缀和判断一个 $a \times a$ 区域是否全 $1$ ，对于每个左上角 $(i, j)$ ，我们都想知道它对应的 $a × a$ 区域里是不是全 $1$ 。用二维前缀和可以做到 $O(1)$ 查询，若某个 $a × a$ 区域内 $1$ 的个数等于 $a \times a$ ，则说明它是合法位置。

把每个合法位置看成图上的一个点，如果两个合法位置上下左右相邻，就连一条边。然后从任意一个合法位置开始 $BFS / DFS$ ，如果最终能访问到所有合法位置，说明它们连通，否则说明无法形成一条路径。

把每个合法位置对应的 $a \times a$ 方块都加进去。为了高效统计覆盖情况，使用二维差分，对每个合法位置 $(x, y)$ ，令它覆盖矩形 $[x, x+a-1] \times [y, y+a-1]$ ，用二维差分把这些矩形全部加上，最后做一次二维前缀和，得到每个格子被覆盖了多少次。如果某个原矩阵里的 $1$ 没有被覆盖到，则 $a$ 不可行。

时间复杂度 $O(nmlog(\min(n,m)))$

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    vector<int> ps((n + 1) * (m + 1), 0);
    auto idx = [&](int x, int y) { return x * (m + 1) + y; };
    for (int i = 0; i < n; ++i) {
        int S = 0;
        for (int j = 0; j < m; ++j) {
            S += g[i][j] == '1';
            ps[idx(i + 1, j + 1)] = ps[idx(i, j + 1)] + S;
        }
    }

    auto calc = [&](int x1, int y1, int x2, int y2) { return ps[idx(x2, y2)] - ps[idx(x1, y2)] - ps[idx(x2, y1)] + ps[idx(x1, y1)]; };

    auto check = [&](int a) {
        int H = n - a + 1;
        int W = m - a + 1;
        if (H <= 0 || W <= 0) return false;

        vector<bool> flag(H * W, 0);
        vector<int> pos;

        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                if (calc(i, j, i + a, j + a) == a * a) {
                    flag[i * W + j] = 1;
                    pos.pb(i * W + j);
                }
            }
        }
        if (pos.empty()) return false;

        vector<bool> vis(H * W);
        queue<int> q;
        q.push(pos[0]);
        vis[pos[0]] = 1;
        int cnt = 1;

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            int x = cur / W, y = cur % W;

            auto add = [&](int nx, int ny) {
                int nxt = nx * W + ny;
                if (flag[nxt] && !vis[nxt]) {
                    vis[nxt] = 1;
                    ++cnt;
                    q.push(nxt);
                }
            };

            if (x > 0) add(x - 1, y);
            if (x + 1 < H) add(x + 1, y);
            if (y > 0) add(x, y - 1);
            if (y + 1 < W) add(x, y + 1);
        }

        if (cnt != pos.size()) return false;

        vector<int> diff((n + 1) * (m + 1), 0);

        for (auto v : pos) {
            int x = v / W, y = v % W;
            diff[idx(x, y)] += 1;
            diff[idx(x + a, y)] -= 1;
            diff[idx(x, y + a)] -= 1;
            diff[idx(x + a, y + a)] += 1;
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int cur = diff[idx(i, j)];
                if (i > 0) cur += diff[idx(i - 1, j)];
                if (j > 0) cur += diff[idx(i, j - 1)];
                if (i > 0 && j > 0) cur -= diff[idx(i - 1, j - 1)];
                diff[idx(i, j)] = cur;
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == '1' && diff[idx(i, j)] <= 0) {
                    return false;
                }
            }
        }

        return true;
    };

    int lo = 1, hi = min(n, m), ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid))
            ans = mid, lo = mid + 1;
        else
            hi = mid - 1;
    }

    cout << ans << endl;
}

C Papy 的数列求和

知识点：二进制字符串逐位 $\text{DP}$ ，数列求和拆项，模运算，构造递推式

要求计算：

f(n,a,b,q)=\sum_{i=1}^{n}\big((ai+b)\cdot q^i\big)\pmod m

把式子拆开：

f(n,a,b,q) = a\sum_{i=1}^{n} i q^i + b\sum_{i=1}^{n} q^i

因此问题本质上变成同时维护两个前缀和：

$S(n)=\sum_{i=1}^{n} q^i$
$T(n)=\sum_{i=1}^{n} i q^i$

最终答案就是：

a\cdot T(n)+b\cdot S(n)\pmod m

由于题目中的 $n$ 是一个二进制整数，长度可达 $5\times 10^6$ ，不能直接转成普通整数，也不能用朴素循环枚举 $1\sim n$ 。所以我们考虑按二进制逐位扩展转移。

设当前已经处理完某个二进制前缀，其对应的数值为 $x$ 。

我们维护四个量：

$x$ ：当前前缀代表的整数值（模 $m$ ），初始 $x=0$ 。
$p=q^x \pmod m$ ，初始 $p=1$ 。
$s_1=S(x)=\sum_{i=1}^{x} q^i \pmod m$ ，初始 $s_1=0$ 。
$s_2=T(x)=\sum_{i=1}^{x} i q^i \pmod m$ ，初始 $s_2=0$ 。

接下来计算转移

如果读到的是 $0$ ，即 $x' = 2x$ ：
- $s_1' = S(2x) = \sum_{i=1}^{2x}q^{i} = \sum_{i=1}^{x}q^i + \sum_{i=x+1}^{2x}q^i = S(x) + q^xS(x) = (1+q^x)S(x) = (1+p)s_1$
- $s_2' = T(2x) = \sum_{i=1}^{2x}iq^i = \sum_{i=1}^{x}iq^i + \sum_{i=x+1}^{2x}iq^i$
  - 其中 $\sum_{i=x+1}^{2x}iq^i = \sum_{j=1}^{x}(x+j)q^{x+j} = p\sum_{j=1}^x(x+j)q^j=px\sum_{j=1}^{x}q^j + p\sum_{j=1}^{x}jq^j = pxS(x)+pT(x)$
  - 故 $s_2' = T(2x) = pxS(x) + (1+p)T(x) = pxs_1 + (1+p)s_2$
- $p' = q^{2x} = (q^{x})^2 = p^2$
如果读到的是 $1$ ，即 $x' = 2x+1$ ：
- $s_1' = S(2x) +p^{2x+1} = (1+p)S(x)+p^2q = (1+p)s_1+p^2q$
- $s_2' = T(2x)+(2x+1)q^{2x+1}=pxS(x)+(1+p)T(x)+(2x+1)p^2q=xps_1 +(1+p)s_2+(2x+1)p^2q$
- $p'=q^{2x+1} = p^2q$

当二进制串全部处理完后，当前的 $x$ 就是 $n$ ，此时：

$s_1 = \sum_{i=1}^{n} q^i$
$s_2 = \sum_{i=1}^{n} i q^i$

所以答案为：

a\cdot s_2+b\cdot s_1 \pmod m

时间复杂度 $O(n)$

void solve() {
    ll mod, a, b, q;
    cin >> mod >> a >> b >> q;
    Z::setMod(mod);
    string n;
    cin >> n;
    Z s1(0), s2(0), p(1), x(0);
    for (auto v : n) {
        if (v == '0') {
            s2 = s2 * (1 + p) + x * p * s1;
            s1 *= 1 + p;
            p *= p;
            x *= 2;
        } else {
            Z np = p * p * q;
            s2 = s2 * (1 + p) + x * p * s1 + (2 * x + 1) * np;
            s1 = s1 * (1 + p) + np;
            p = np;
            x = 2 * x + 1;
        }
    }
    cout << a * s2 + b * s1 << endl;
}

D Kendieer 的 LCP 问题

知识点：字典序排序，LCP，RMQ / Sparse Table，单调栈，贡献法 / 计数法，组合计数

先把所有字符串按字典序全局排序，记排序后的编号为 $ord[1..n]$ 。设相邻两个字符串 $ord[i]$ 和 $ord[i+1]$ 的 $\text{LCP}$ 长度为：

g_i = \operatorname{LCP}(s_{ord[i]}, s_{ord[i+1]})

形成一个长度为 $n-1$ 的数组。

对于任意两个在全局字典序中位置分别为 $l<r$ 的字符串，有：

\operatorname{LCP}(s_{ord[l]}, s_{ord[r]}) = \min(g_l, g_{l+1}, \dots, g_{r-1})

所以，查询里若选出的字符串在全局排序后的下标为 $p_1<p_2<\dots<p_k$ ，那么该子集的 $\text{LCP}$ 长度就是：

\min\big( \operatorname{LCP}(p_1,p_2), \operatorname{LCP}(p_2,p_3), \dots, \operatorname{LCP}(p_{k-1},p_k) \big)

于是问题变成：

对每个查询给出的 $k$ 个位置，排序后得到一个长度为 $k$ 的序列；
每个非空子集的贡献，等价于这组点对应的相邻间隔 $\text{LCP}$ 的最小值；
统计所有非空子集的最小值之和。

若子集大小为 $1$ ，则 $\text{LCP}$ 就是该字符串本身长度。因此先把查询中所有字符串长度加起来：

\text{tot} = \sum |s_{idx_i}|

若子集大小 $\geq 1$ ，设查询中排序后的字符串位置为 $ranks[0..k-1]$ 。定义：

L_i = \operatorname{LCP}(ranks[i-1], ranks[i]) \quad (1 \le i \le k-1)

全局字典序排序后，任意两串 $x<y$ 的 $\text{LCP}$ 等于它们在排序序列中间所有相邻 $\text{LCP}$ 的最小值：

\operatorname{LCP}(x,y)=\min(g_x,g_{x+1},\dots,g_{y-1})

所以 $L_i$ 可以通过全局 $g$ 数组的 $\text{RMQ}$ 在 $O(1)$ 时间求得。

接下来只需要统计：所有非空子集里，最小间隔恰好由某个 $L_i$ 贡献的子集数量。对每个间隔 $i$ （即 $L_i$ ），我们要找到它作为最小值的最大影响范围。

我们用单调栈求：

$left[i]$ ：使得在区间 $[left[i], i]$ 内， $L_i$ 是严格最小的位置；
$right[i]$ ：使得在区间 $[i, right[i]]$ 内， $L_i$ 仍可作为最小值的最右范围。

左边维护严格单调递增栈，遇到 $>$ 弹出，右边维护单调递增栈，遇到 $\geq$ 弹出。这样处理相等值时，统一把贡献分配给最左边的那个最小值，避免重复统计。

若 $L_i$ 作为一个子集 $\text{LCP}$ 的主导最小值，那么这个子集必须：

左侧至少选一个字符串；
右侧至少选一个字符串；
选中的字符串都必须落在 $L_i$ 的有效区间内。

因此：

左侧可选字符串个数为 $i - left[i] + 1$
右侧可选字符串个数为 $right[i] - i + 1$

各自必须非空，故方案数为：

(2^{i-left[i]+1} - 1)\cdot (2^{right[i]-i+1} - 1)

于是 $L_i$ 的贡献就是：

L_i \cdot (2^{i-left[i]+1} - 1)\cdot (2^{right[i]-i+1} - 1)

把所有 $i=1..k-1$ 的贡献加起来，再加上单点子集的字符串长度和，就是答案。

vector<Z> p2(1);
void init() {
    p2[0] = 1;
    for (int i = 1; i <= 500000; ++i) p2.pb(p2.back() * 2);
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; ++i) cin >> s[i];

    vector<int> ord(n);
    iota(all(ord), 1);
    sort(all(ord), [&](int a, int b) { return s[a] < s[b]; });
    vector<int> pos(n + 1);
    for (int i = 0; i < n; ++i) pos[ord[i]] = i;

    auto get = [&](string a, string b) {
        int len = min(a.size(), b.size());
        for (int i = 0; i < len; ++i) {
            if (a[i] != b[i]) return i;
        }
        return len;
    };
    vector<int> lcp(max(1, n - 1));
    for (int i = 0; i < n - 1; ++i) {
        lcp[i] = get(s[ord[i]], s[ord[i + 1]]);
    }

    int N = n <= 1 ? 1 : __lg(n - 1) + 1;
    vector<array<int, 18>> spt(n - 1);
    for (int i = 0; i < n - 1; ++i) spt[i][0] = lcp[i];

    for (int j = 1; j < N; ++j) {
        for (int i = 0; i + (1 << j) <= n - 1; ++i) {
            spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
        }
    }

    auto ask = [&](int L, int R) {
        int j = __lg(R - L + 1);
        return min(spt[L][j], spt[R - (1 << j) + 1][j]);
    };

    while (q--) {
        int k;
        cin >> k;
        vector<int> idx(k);
        for (int i = 0; i < k; ++i) cin >> idx[i];

        vector<int> ranks(k);
        for (int i = 0; i < k; ++i) ranks[i] = pos[idx[i]];
        sort(all(ranks));

        Z tot = 0;
        for (int i = 0; i < k; ++i) tot += s[ord[ranks[i]]].size();

        if (k == 1) {
            cout << tot << " ";
            continue;
        }

        vector<int> L(k);
        for (int i = 1; i < k; ++i) {
            L[i] = ask(ranks[i - 1], ranks[i] - 1);
        }

        vector<int> left(k), right(k), stk;

        for (int i = 1; i < k; ++i) {
            while (!stk.empty() && L[stk.back()] > L[i]) stk.pob();
            left[i] = stk.empty() ? 1 : stk.back() + 1;
            stk.pb(i);
        }

        stk.clear();
        for (int i = k - 1; i >= 1; --i) {
            while (!stk.empty() && L[stk.back()] >= L[i]) stk.pob();
            right[i] = stk.empty() ? k - 1 : stk.back() - 1;
            stk.pb(i);
        }

        for (int i = 1; i < k; ++i) tot += Z(L[i]) * (p2[i - left[i] + 1] - 1) * (p2[right[i] - i + 1] - 1);

        cout << tot << " ";
    }
    cout << endl;
}

E CirnoNine 找凸四边形

知识点：计算几何，叉积 / 方向判断，Andrew 凸包，凸包层剥离

先猜一个剥几层凸包下来，一定能在产生的点集中找到凸四边形，就有：

对点集求凸包，如果凸包的点数 $\geq 4$ ，那么输出四个点即可。
如果本层点数 $\leq 3$ ，那么我们把点加入最终暴力枚举的点集中。
最终枚举四个点，检查这四个点是否能够组成凸四边形即可。

接下来我们证明如果存在凸四边形，在前三层中一定能够找到合法的一组答案：

设在所有凸四边形里，取一个使“四个顶点中最大层数”尽量小的，记为 $A,B,C,D$ ，并设 $D$ 是其中最深的顶点。若 $D$ 已经在前三层里，结论成立；下面假设 $D$ 在第 $4$ 层及以后。

因为第 $4$ 层及以后一定在前三层点集 $K=L_1\cup L_2\cup L_3$ 的凸包里，所以 $D\in \operatorname{conv}(K)$ 。由二维 $Carathéodory$ 定理，存在 $X,Y,Z\in K$ ，使得 $D\in \triangle XYZ$ .

现在固定四边形的另外三个点 $A,B,C$ 。能作为第四个点、并且仍与 $A,B,C$ 构成同向凸四边形的点，构成一个开凸区域 $W$ ；而 $D\in W$ 。

这里用一个交换引理：

如果一个点 $D$ 在凸区域 $W$ 内，同时 $D$ 又在某个三角形 $\triangle XYZ$ 内，那么只要 $D$ 是某个凸四边形的可替换顶点，就可以在 $X,Y,Z$ 中找到一个点 $P\in W$ 。于是用 $P$ 替换 $D$ 后，仍然得到凸四边形，而且 $P$ 来自前三层。

这样就得到一个“最深层数更小”的凸四边形，和我们取的最优性矛盾。

因此，假设不成立，说明最优凸四边形的四个顶点都能放到前三层里。结论成立。

template <class Int>
struct Point {
    Int x, y;
    int id;
    Point(const Int &x_ = 0, const Int &y_ = 0) : x(x_), y(y_) {}
    bool operator<(const Point &o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }
};

template <class Int>
Int cross(const Point<Int> &a, const Point<Int> &b, const Point<Int> &c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

template <class Int>
vector<Point<Int>> convex(vector<Point<Int>> pts) {
    int n = pts.size();
    if (n <= 2) return pts;

    sort(all(pts));

    vector<Point<Int>> hull;

    for (int i = 0; i < n; ++i) {
        while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }
    int ls = hull.size();
    for (int i = n - 2; i >= 0; --i) {
        while (hull.size() > ls && cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }
    if (hull.size() > 1) hull.pop_back();
    return hull;
}

void solve() {
    int n;
    cin >> n;
    vector<Point<ll>> pts(n);
    for (int i = 0; i < n; i++) cin >> pts[i].x >> pts[i].y, pts[i].id = i + 1;

    sort(all(pts));

    vector<bool> vis(n + 1);
    vector<Point<ll>> cand;

    for (int i = 0; i < 3; ++i) {
        vector<Point<ll>> cur;
        for (auto v : pts) {
            if (!vis[v.id]) cur.pb(v);
        }

        if (cur.size() < 3) {
            for (auto v : cur) cand.pb(v);
            break;
        }

        auto hull = convex(cur);
        if (hull.size() >= 4) {
            cout << hull[0].id << " " << hull[1].id << " " << hull[2].id << " " << hull[3].id << "\n";
            return;
        }

        for (auto v : hull) {
            vis[v.id] = true;
            cand.pb(v);
        }
    }

    int m = cand.size();
    if (m >= 4) {
        sort(all(cand));
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                for (int k = j + 1; k < m; ++k) {
                    for (int l = k + 1; l < m; ++l) {
                        vector<Point<ll>> sub = {cand[i], cand[j], cand[k], cand[l]};
                        vector<Point<ll>> shull = convex(sub);
                        if (shull.size() == 4) {
                            for (int it = 0; it < 4; ++it) {
                                cout << shull[it].id << " ";
                            }
                            cout << endl;
                            return;
                        }
                    }
                }
            }
        }
    }

    cout << -1 << endl;
}

F MuQ 的魔咒

知识点：贪心，字典序，后缀数组 / 后缀排名比较，线段树 + 懒标记，区间维护与动态选择，字符串分段处理

要求从原串 $s$ 中选出恰好 $k$ 个互不相交的非空子串，按原顺序拼接后，使得到的新字符串字典序最大。

本题的核心不是“选哪些区间”，而是：

在字典序比较下，尽量让前面的字符更大
如果前缀相同，就尽量让后面的部分更优
由于区间不能重叠，因此一旦某段字符被纳入答案，它对后续可选位置会产生影响

因此可以把问题理解成一个“按字典序贪心选择若干连续块”的过程。

有如下观察：

字典序比较是“从前往后，先看更大的字符”，所以答案的构造一定是贪心的，即在当前还没处理的部分里，优先考虑字典序更大的字符。
当当前字符相同的时候，要比较的是后缀，比如两个候选区间都以 $\text{c}$ 开头，那么谁更优，不是看 $\text{c}$ ，而是看，这段字符后面接什么，也就是比较它们的后缀字典序 -这就需要一个可以快速比较任意两个后缀大小的数据结构。
区间的“同字符连续段”可以整体处理对于某个字符 c，在当前未处理部分中，它会形成若干个连续段。这些连续段是当前层面上的候选块，如果某个段左边已经接上了之前选过的位置，那它通常必须整段吸收，如果候选段太多，则需要按照后缀大小挑出最优的若干段

我们对原串建立后缀数组，得到每个位置 $i$ 的后缀排名 $rk[i]$ 。这样就能在 $O(1)$ 时间内比较两个后缀， $rk[x] > rk[y]$ ，说明 $s[x..]$ 的字典序更大。所以比较时如果两个候选段首字符相同，就直接比较它们的后缀排名，决定保留哪个。

按字符从 $\text{z}$ 到 $\text{a}$ 扫描。对当前字符 $c$ ：

找出当前尚未选过的所有 $c$ 的连续段
如果某段左侧紧挨着已经选过的位置，那么这段通常要直接并入答案
若当前段数超过剩余可用配额，则按后缀排名排序，保留更优的段
对于最终保留下来的段，直接把其中字符全部加入答案

直观理解就是：

先尽量让答案前面出现更大的字母
同字母时，优先保留后缀更大的段
不能保留的段，就尽量完整地吸收掉，避免浪费位置

对于维护和查询后缀排名，我们使用线段树。每个位置的叶子节点存当前字符大小和当前位置编号，比较规则即为：先比字符大小，字符相同再比位置。

当位置 $x$ 被选入答案时：

将 $x$ 标记为已选
修改区间 $[x, n]$ 的优先级，让后续查询更倾向于从右侧继续选取合适字符

这样可以在动态删除/选择位置的同时，仍然快速找到当前最优的剩余位置。

时间复杂度： $O(n log n)$

struct SegTree {
    struct Node {
        int l = 0, r = 0;
        array<ll, 3> val{0, 0, -1};
        ll lazy = 0;
    };
 
    int n = 0;
    vector<Node> tr;
 
    static array<ll, 3> mergeVal(const array<ll, 3>& a, const array<ll, 3>& b) {
        if (a[2] == -1) return b;
        if (b[2] == -1) return a;
        return min(a, b);
    }
 
    void pull(int u) { tr[u].val = mergeVal(tr[u << 1].val, tr[u << 1 | 1].val); }
 
    void apply(int u, ll add) {
        tr[u].lazy += add;
        tr[u].val[0] += add;
    }
 
    void push(int u) {
        if (!tr[u].lazy) return;
        apply(u << 1, tr[u].lazy);
        apply(u << 1 | 1, tr[u].lazy);
        tr[u].lazy = 0;
    }
 
    void build(int u, int l, int r, const vector<int>& a) {
        tr[u].l = l;
        tr[u].r = r;
        tr[u].lazy = 0;
        if (l == r) {
            tr[u].val = {0, -(ll)a[l], l};
            return;
        }
        int m = (l + r) >> 1;
        build(u << 1, l, m, a);
        build(u << 1 | 1, m + 1, r, a);
        pull(u);
    }
 
    void build(const vector<int>& a) {
        n = (int)a.size() - 1;
        tr.assign(4 * n + 5, {});
        build(1, 1, n, a);
    }
 
    void update(int u, int l, int r, int ql, int qr, ll add) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            apply(u, add);
            return;
        }
        push(u);
        int m = (l + r) >> 1;
        update(u << 1, l, m, ql, qr, add);
        update(u << 1 | 1, m + 1, r, ql, qr, add);
        pull(u);
    }
 
    void update(int l, int r, ll add) { update(1, 1, n, l, r, add); }
 
    array<ll, 3> query(int u, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return {0, 0, -1};
        if (ql <= l && r <= qr) return tr[u].val;
        push(u);
        int m = (l + r) >> 1;
        return mergeVal(query(u << 1, l, m, ql, qr), query(u << 1 | 1, m + 1, r, ql, qr));
    }
 
    array<ll, 3> query(int l, int r) { return query(1, 1, n, l, r); }
};
 
struct SuffixArray {
    int n = 0;
    vector<int> sa, rk, tmp, cnt;
 
    void build(const string& s) {
        n = (int)s.size() - 1;
        sa.assign(n + 1, 0);
        rk.assign(n + 1, 0);
        tmp.assign(n + 1, 0);
        cnt.assign(max(256, n) + 5, 0);
 
        int m = 256;
        fill(cnt.begin(), cnt.begin() + m, 0);
 
        for (int i = 1; i <= n; ++i) cnt[rk[i] = (unsigned char)s[i]]++;
        for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
 
        for (int len = 1, p = 0; p < n; len <<= 1) {
            p = 0;
            for (int i = max(1, n - len + 1); i <= n; ++i) tmp[++p] = i;
            for (int i = 1; i <= n; ++i)
                if (sa[i] > len) tmp[++p] = sa[i] - len;
 
            fill(cnt.begin(), cnt.begin() + m, 0);
            for (int i = 1; i <= n; ++i) cnt[rk[tmp[i]]]++;
            for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; --i) sa[cnt[rk[tmp[i]]]--] = tmp[i];
 
            tmp[sa[1]] = 1;
            p = 1;
            for (int i = 2; i <= n; ++i) {
                int a = sa[i], b = sa[i - 1];
                int ra = rk[a], rb = rk[b];
                int r1 = (a + len <= n ? rk[a + len] : 0);
                int r2 = (b + len <= n ? rk[b + len] : 0);
                if (ra == rb && r1 == r2)
                    tmp[a] = p;
                else
                    tmp[a] = ++p;
            }
            for (int i = 1; i <= n; ++i) rk[i] = tmp[i];
            m = p + 1;
            if (p == n) break;
        }
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = ' ' + s;
 
    SuffixArray SA;
    SA.build(s);
 
    vector<int> rankv(n + 1);
    for (int i = 1; i <= n; ++i) rankv[i] = SA.rk[i];
 
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) a[i] = s[i];
 
    SegTree tr;
    tr.build(a);
 
    auto betterSuffix = [&](int x, int y) { return rankv[x] > rankv[y]; };
 
    vector<char> vis(n + 1, 0);
    vector<int> lenCnt(n + 1, 0);
    int bucketCnt = 0;
    int now = 1, cnt = 0, remain = k;
 
    auto sel = [&](int x) {
        tr.update(x, n, -1);
        tr.update(x, x, (ll)n * 10);
        vis[x] = 1;
        ++cnt;
    };
 
    for (char c = 'z'; c >= 'a' && now <= n; --c) {
        vector<pii> seg;
        for (int i = now; i <= n; ++i) {
            if (vis[i] || s[i] != c) continue;
            if (i == now || s[i - 1] != c)
                seg.push_back({i, i});
            else
                seg.back()[1] = i;
        }
 
        if (seg.empty()) continue;
 
        if (vis[seg[0][0] - 1]) {
            for (int i = seg[0][0]; i <= seg[0][1]; ++i) sel(i);
            seg.erase(seg.begin());
        }
 
        if ((int)seg.size() > remain) {
            auto ord = seg;
            sort(ord.begin(), ord.end(), [&](const pii& A, const pii& B) { return betterSuffix(A[0], B[0]); });
 
            int tmpLen = 0;
            for (int i = 0; i < remain; ++i) {
                auto [l, r] = ord[i];
                if (lenCnt[r - l]++ == 0) ++bucketCnt;
                tmpLen = r - l;
            }
 
            vector<pii> keep;
            int j = 0;
            for (; j < (int)seg.size(); ++j) {
                auto [l, r] = seg[j];
                if (lenCnt[r - l] == 0) continue;
                if (--lenCnt[r - l] == 0) --bucketCnt;
 
                if (r - l == tmpLen) {
                    keep.push_back({l, r});
                } else {
                    for (int i = l; i <= r; ++i) {
                        sel(i);
                        now = max(now, i + 1);
                    }
                    --remain;
                }
                if (bucketCnt == 0) break;
            }
 
            seg[j][0] = seg[j][1] - tmpLen;
            pii best = seg[j];
            for (int i = j + 1; i < (int)seg.size(); ++i) {
                if (betterSuffix(seg[i][0], best[0])) best = seg[i];
            }
 
            if (best != seg[j]) {
                keep.pop_back();
                keep.push_back(best);
            }
 
            for (auto [l, r] : keep) {
                for (int i = l; i <= r; ++i) {
                    sel(i);
                    now = max(now, i + 1);
                }
                --remain;
            }
 
            while (now <= n) sel(now++);
        } else {
            for (auto [l, r] : seg) {
                for (int i = l; i <= r; ++i) {
                    sel(i);
                    now = max(now, i + 1);
                }
                --remain;
            }
        }
    }
 
    while (cnt < k) {
        int id = tr.query(1, n)[2];
        sel(id);
    }
 
    for (int i = 1; i <= n; ++i)
        if (vis[i]) cout << s[i];
    cout << endl;
}

G 矩阵的秩

知识点：有限域上的线性代数， $q-$ 模拟与高斯二项式系数， $q-$ 反演，多项式分治卷积， $Chirp-Z$ 变换（等比数列多点求值），多项式卷积

在有限域 $\mathbb{F}_p$ 中，长度为 $m$ 的非零向量共有 $p^m−1$ 个。两个向量 $v,w$ 成比例（ $v=λw,λ\neq 0$ ）当且仅当它们属于同一个一维子空间。在 $\mathbb{F}_p^m$ 中，共有 $N=\frac{p^m−1}{p−1}$ 个不同的一维子空间。

矩阵的 $n$ 个行向量互不成比例，意味着这 $n$ 个行向量必须属于 $n$ 个不同的一维子空间。

设我们在射影空间 $PG(m−1,\mathbb{F}_p)$ 中选择了 $n$ 个不同的点（每个点对应一个一维子空间）。我们需要计算这 $n$ 个点生成的张成空间的维数为 $k$ 的方案数。

设 $E_k$ 为在射影空间中选择 $n$ 个不同点且张成空间维数为 $k$ 的有序序列数。根据 $q-$ 反演公式，总方案数为：

ans(k) =(p−1)^n\binom{m}{k}_p\sum_{j=0}^k(−1)^{k−j}p^{\binom{k-j}{2}}\binom{k}{j}_pP(N_j,n)

其中：

$\binom{m}{k}_p = \frac{\prod_{i=1}^{m}(p^i-1)}{\prod_{i=1}^{k}(p^i-1)\prod_{i=1}^{m-k}(p^i-1)}$ 是高斯二项式系数。
$N_j=\frac{p^j-1}{p-1}$ 是 $j$ 维向量空间中一维子空间的数量。
$P(x,n) = x(x−1)…(x−n+1)$ 是下降阶乘幂，也就是排列数。

$P(N_j,n)=\prod_{i=0}^{n−1}(\frac{p^j−1}{p-1}−i)=\frac{1}{(p−1)^n}\prod_{i=0}^{n−1}(p^j−1−i(p−1))$ 。设 $Poly(X)=\prod_{i=0}^{n−1}(X−(1+i(p−1)))$ 。我们可以用分治 + $NTT$ 在 $O(nlog⁡2n)$ 内求出该多项式的系数。

利用 $Chirp-Z$ 变换，我们可以在 $O((n+m)log(n+m))$ 内求出所有 $Poly(p_j)$ 。

最后通过一次卷积即可求出所有的 $ans(k)$ 。

template <ll G>
struct Poly {
    static void ntt(vector<Z> &a, bool invert) {
        int n = a.size();
        vector<int> rev(n);
        int lg = __builtin_ctz(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < lg; j++)
                if (i & (1 << j)) rev[i] |= 1 << (lg - 1 - j);
            if (i < rev[i]) swap(a[i], a[rev[i]]);
        }
 
        for (int len = 2; len <= n; len <<= 1) {
            Z wlen = ksm(Z(G), (MOD - 1) / len);
            if (invert) wlen = Z(1) / wlen;
            for (int i = 0; i < n; i += len) {
                Z w = 1;
                for (int j = 0; j < len / 2; j++) {
                    Z u = a[i + j], v = a[i + j + len / 2] * w;
                    a[i + j] = u + v;
                    a[i + j + len / 2] = u - v;
                    w *= wlen;
                }
            }
        }
 
        if (invert) {
            for (auto &x : a) x /= n;
        }
    }
    static vector<Z> multiply(vector<Z> a, vector<Z> b) {
        int res_deg = a.size() + b.size() - 2;
        int sz = 1;
        while (sz < a.size() + b.size()) sz <<= 1;
        a.resize(sz);
        b.resize(sz);
        ntt(a, false);
        ntt(b, false);
        for (int i = 0; i < sz; i++) a[i] *= b[i];
        ntt(a, true);
        a.resize(res_deg + 1);
        return a;
    }
};
 
using NTT = Poly<3>;

void solve() {
    int n, m, p;
    cin >> n >> m >> p;
 
    int K = min(n, m), N = max(n, m);
 
    vector<Z> pow(N + 1);
    pow[0] = 1;
    for (int i = 1; i <= N; ++i) pow[i] = pow[i - 1] * p;
 
    vector<Z> fac(N + 1), invfac(N + 1);
    fac[0] = 1;
    for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * (pow[i] - 1);
    invfac[N] = Z(1) / fac[N];
    for (int i = N - 1; i >= 0; --i) invfac[i] = invfac[i + 1] * (pow[i + 1] - 1);
 
    vector<Z> d(n);
    for (int i = 0; i < n; ++i) d[i] = Z(i) * (p - 1) + 1;
    auto build = [&](auto &&self, int L, int R) -> vector<Z> {
        if (L == R) return {-d[L], 1};
        int mid = (L + R) / 2;
        return NTT::multiply(self(self, L, mid), self(self, mid + 1, R));
    };
 
    vector<Z> coeffs = build(build, 0, n - 1);
 
    int tot = n + K;
    vector<Z> pw(tot + 1);
    pw[0] = 1;
    Z pp = 1;
    for (int i = 1; i <= tot; ++i) pw[i] = pw[i - 1] * pp, pp *= p;
 
    vector<Z> xr(n + 1), yt(tot + 1);
    for (int a = 0; a <= n; ++a) xr[n - a] = coeffs[a] / pw[a];
    for (int i = 0; i <= tot; ++i) yt[i] = pw[i];
 
    vector<Z> ce = NTT::multiply(xr, yt), pj(K + 1);
    for (int j = 0; j <= K; ++j) pj[j] = ce[n + j] / pw[j];
 
    vector<Z> A(K + 1), B(K + 1);
    for (int i = 0; i <= K; ++i) A[i] = ((i & 1) ? -1 : 1) * (pw[i] * invfac[i]), B[i] = pj[i] * invfac[i];
 
    vector<Z> fin = NTT::multiply(A, B);
    for (int k = 0; k <= K; ++k) cout << fin[k] * fac[m] * invfac[m - k] << " ";
    cout << endl;
}