本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-08 20:37:11

很明显就是线段树维护区间次小值的出现次数。

这里主要讲怎么把 push_up 写的简洁一些。

node
push_up (const node &l, const node &r)
{
  vector<pi> z; z.reserve (4);
  
  z.emplace_back (l.mx), z.emplace_back (l.pmx);
  z.emplace_back (r.mx), z.emplace_back (r.pmx);
  sort (begin (z), end (z), greater<pi> ());
  for (auto p = begin (z); p != prev (end (z)); p++)
    if (p->first == next (p)->first) p->second += next (p)->second;
  return { z[0], z[1].first == z[0].first ? z[2] : z[1] };
}

某些人写了六十行的大模拟还没调过

我们可以把值和出现次数捆绑在一起维护，这样就可以方便更新。先排序，然后维护一下出现次数即可。

完整代码（只有 74 行）

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-21 15:05:14

和机房 dalao 在机房黑板上推了式子，但是不如队爷 cxm 的简洁，替他 写个题解。

这题和百事世界杯那道很像，区别就是这题是有两个人的。 但是状态是一样的。

我们设 $f(x)$ 表示作为先手，当前有 $x$ 个物品已经被摸到的期望代价，同理设 $g(x)$ 代表后手的相应情况。（用 $i$ 做变量的话推式子老觉得跟复分析一样qwq）

对于每一次摸球，我们只有摸到新的和摸到旧的两种可能。

• 摸到新的，概率是 $\dfrac {n - x} n$，此时有

$$\begin{cases} f(x) = g(x + 1), \ g(x) = f(x + 1) \end{cases}$$

• 摸到旧的，概率是 $\dfrac x n$，此时

$$\begin{cases} f(x) = g(x) + 1, \ g(x) = f(x) \end{cases}$$

这个先后手的转移有一点抽象。当前的先手，转移之后自然是后手，反之亦然。这里玩家并没有改变，仍然是 A 和 B，只是先后手的顺序改变了。我们用状态，用的就是它的语义。

联立这个方程，得到解：

$$\begin{cases} f(x) = \bigg(\dfrac {n - x} n \cdot g(x + 1) + \dfrac{x\cdot (n - x)}n \cdot f(x + 1) + \dfrac x n\bigg) \bigg/ \bigg(1 - \dfrac {x^2}{n^2}\bigg) \ g(x) = \dfrac x n \cdot f(x) + \dfrac{n - x}n \cdot f(x + 1) \end{cases}$$

倒着递推就行了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-28 17:24:24

卢卡斯定理即

$${n \choose m} \equiv {\lfloor n/p \rfloor \choose \lfloor m/p\rfloor} \cdot {n \bmod p \choose m \bmod p} \pmod p$$

其中 $p$ 是质数

我们用二项式定理证明。

首先，$p$ 是质数，则 $${p\choose n} = p n^{-1} {p-1 \choose n-1} \equiv 0 \pmod p$$

然后有

$$(x+1)^p = \sum\limits_{j=0}^p {p \choose j} x^j \equiv x^p + 1 \pmod p$$

然后构造

$$ \begin{aligned} (x + 1)^m &\equiv (x+1)^{p\lfloor m / p\rfloor + (m \bmod p)} \ &\equiv (x^p + 1)^{m/p} (x+1)^{m \bmod p} \ &\equiv \sum\limits_{j=0}^{\lfloor m/p\rfloor} {\lfloor m/p\rfloor \choose j}x^{jp} \cdot \sum\limits_{k=0}^{m\bmod p}{m \bmod p \choose k}x^k \ &\equiv \sum\limits_{k=0}^{m} {\lfloor m/p\rfloor \choose \lfloor m/k\rfloor}{m \bmod p \choose k \bmod p} \pmod p \end{aligned} $$

又有

$$(x+1)^m =\sum\limits_{k=0}^m {m\choose k}x^k$$

按系数，得证：

$${\lfloor m/p\rfloor\choose \lfloor m/k\rfloor}{m\bmod p\choose k\bmod p} \equiv {m\choose k} \pmod p$$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 09:07:04

例题 P4198 楼房重建

题意即，求整个序列中前缀最大值的数量。

考虑线段树能否维护。首先维护一个区间答案，然后考虑怎么动态维护。

线段树动态维护的方法，就是考虑左右区间的贡献，得到一个大区间的答案，然后向上递归。

那么，在这个题目里，左右区间的贡献怎么计算？

首先显然，右对左是没有贡献的。左对右的贡献，看起来很不好计算。我们来分类讨论：

• 左极值如果大于右极值，那么右边答案就是零

• 左极值如果小于右极值，这时候还不好得出结论。我们继续分讨：

• 左极值大于右左区间的极值，那么右左区间答案是零，我们在右右区间上递归

• 否则，我们考虑：既然左极值小于右左区间极值，那么右右区间受它的的影响，一定是不如受右左区间的影响的。换句话说，右右区间受不到左极值的影响。这时候，右区间的答案，就是右右区间的答案加上右左区间上递归得到的答案。

在这道题中，我们为了计算左右区间之间的贡献，需要另外做一次递归。换句话说，我们的 pushup 是 $O(\log n)$ 的。这样，一次点修的复杂度 $O(\log^2 n)$。

例题 [FJOI2016] 神秘数

题意为：求出最小的不能被区间 $[l, r]$ 子集的和表示出来的数。

我们先想一下暴力怎么做。

我们维护一个 $p$，表示 $[1, p)$ 的数都能表示出来。初始地，$p = 1$。

我们考虑怎么表示出 $p$。显然，能表示出 $p$，当且仅当存在 $u \le p$。如果找得到这样的 $u$，$p\gets p + u$。否则，答案就是 $p$。

我们考虑怎么加速。

首先更新以下策略：每次找小于等于 $p$ 的数之和 $q$。如果这个和大于等于 $p$，由于所有的数都是小于 $p$ 的，我们显然可以表示出 $q$ 以内的所有数。此时 $p \gets q + 1$。否则,我们同样能得出答案 $p$。

这个过程是 $O(\log V)$ 的，但很松。

我们再审视一下这个问题：找小于等于 $p$ 的数之和，这就是主席树板子，在 $O(\log V)$ 的时间可以做到。于是整体时间是很松的 $O(\log^2 V)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 15:25:13

题意明确。

$$ \begin{aligned} \mathrm{圆柿} &= \sum\limits_{p \in \mathrm{primes}}\sum\limits_{i=0}^n\sum\limits_{j=0}^m [(i, j) = p] \ &= \sum\limits_{p \in \mathrm{primes}}\sum\limits_{i=0}^n\sum\limits_{j=0}^m\sum\limits_{d\mid (i,j)} \mu(d) \ &=\sum\limits_{p\in\mathrm{primes}}\sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m [d\mid i][d \mid j] \ &= \sum\limits_{p\in\mathrm{primes}}\sum\limits_{d=1}^{\min(n, m)}\mu(d)\lfloor\dfrac n {pd}\rfloor\lfloor\dfrac m {pd}\rfloor \end{aligned} $$

最开始只得到了这个 $O(Tn)$ 的做法，爆零。但是可以再优化一下。设 $u = pd$，则

$$ \begin{aligned} 圆柿 = \sum\limits_{u=1}^{\min(n, m)}\lfloor{\dfrac n u}\rfloor\lfloor\dfrac m u\rfloor\sum\limits_{d\mid u}\mu(\dfrac u d) \end{aligned} $$

然后惊奇地发现后面的柿子可以 $O(V)$ 预处理！

于是本题就用优雅的 $O(V + T\sqrt n)$ 复杂度做完了

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-02 20:47:40

对顶堆可以处理动态第 $k$ 大等问题（$k$ 是常数）。

如果不用对顶堆，我们可以用平衡树解决这个问题，但是常数一般比前者大 2~3 倍（我的实现）。

对顶堆实际上是两个堆，一个大根，一个小根。每个堆自己的单调性是显然的，而我们同样要维护堆之间的单调性：小根堆的最小是大于大根堆的最大的。

就算这样又怎么样？没法怎么样。为了快速得到第 $k$ 大，我们需要保证大根堆里头只有 $k - 1$ 个元素。这样，每一次我们取小根堆的头就可以了。

如果要维护动态中位数，也是可以的，只需要保证两个根的大小差是不超过 1 的即可，中位数就是较大的堆的根。

有人将对顶堆形容为一个沙漏，让人印象很深。但是，如果看成是两个梯形躺在地上，左边是大根堆，右边是小根，中间是分界线，而小根的顶大于大根的顶，应该更形象。

于是我们就维护出了动态第 $k$ 大。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-04 16:09:08

题意还是比较明确的。首先我们需要知道异或的两个性质：$a\oplus a = 0$ 与 $a\oplus 0 = a$。

遇到没思路的时候，先来看几个栗子：

• $(1000)_2 + 1 = (0001)_2$，$k$ 从 $(3)$ 变成 $(0, 3)$，那么 $f(u + 1) = f(u) \oplus a_0$。

• $(0011)_2 + 1 = (0100)_2$，$k$ 从 $(0, 1)$ 变成 $2$，$f(u + 1) = f(u) \oplus a_0 \oplus a_1 \oplus a_2$。

• $(1111)_2 + 1 = (10000)_2$，$k$ 从 $(0, 1, 2, 3)$ 变成 $(4)$，$f(u + 1) = f(u) \oplus a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4$。

观察到：如果 $u + 1$ 进了 $k$ 位，就有 $f(u + 1) = f(u)\oplus \sigma_k$，其中 $\sigma_k = \bigoplus\limits_{i=0}^k a_i$，即 $a$ 的前缀异或和。由题意，$f(u + 1) = f(u)$，故 $\sigma_k = 0$。然后考虑怎么统计答案。

如果 $u + 1$ 进了 $k$ 位，就意味着它的低 $k$ 位全都是 $1$，那么就剩下 $n - k - 1$ 位可以选，也就是 $2^{n - k - 1}$ 种方案。

换句话说，每一个 $\sigma_k = 0$ 的 $k$，都会产生 $2^{n - k - 1}$ 的贡献。 题意中让我们输出二进制表示，于是我们将答案的第 $n - k - 1$ 位置一即可。

最后考虑一个边缘情况：$\sigma_n = 0$，即样例二。这种情况特判，将最终答案加一即可。

赛时码：

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int res[N];

int main (void)
{
    int t;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> t;
    while (t--) {
        int n, sum = 0, high = 0;

        cin >> n;
        for (int i = 0; i <= n; i++) {
            int v;
            cin >> v;
            if ((sum ^= v) == 0 && i < n) res[n - i - 1] = 1, high = max (high, n - i - 1);
        }

        if (!sum) {
            int q = 0;
            while (res[q]) res[q++] = 0;
            res[q] = 1;
        }
        for (int i = high; i >= 0; i--) cout << res[i];
        cout << '\n';
        for (int i = 0; i <= high; i++) res[i] = 0;
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-07 16:53:22

我们首先用重心做根，那么有一个结论：将非根点 $u$ 子树内的边断开，不可能让 $u$ 是重心，用树的重心性质比较好证。

然后，我们设被删掉的另一部分的大小为 $m$，则 $2h_u \le n - m$ 且 $2(n - m - s_u) \le n - m$，化简得到： $m \in [n - 2s_u, n - 2h_u]$。

考虑 $m$ 是怎么来的。我们设 $(w, v)$ 是被删掉的边（$v$ 更深），两种情况：

• $v$ 和 $u$ 在同一条链上，那么 $m = n - s_v$
• 否则，$m = s_v$

我们将所有 $s$ 放到树状数组中，然后在 DFS 的过程中加入 $n - s_v$，DFS 结束时候删除，于是就可以得到答案。

怎么处理子树内的边？我们维护另一棵树状数组，然后计算进入进出子树的差值即可。

根的贡献需要特殊计算，我们分两种情况：

• 删掉的 $v$ 在重儿子子树上，那么要求次重链的长度 $2h' \le n - s_v$
• 否则，$2h \le n - s_v$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-09 21:11:28

做的大概是第二到第三道基环树的题，明显对环的一系列操作不熟悉。

我们知道，作为有向图，要做到两点互相连通，一定是形成一个环。同时显然，题目中所给的是一个基环森林，我们需要把每个基环树断成链，然后把它们首尾相接就可以了。具体断哪条边，需要在环上 DP。

按照基环树的一般策略，把环当作根，然后对环上每一个点跑树形 DP，把重链抽出来显然是最优的。我们可以计算其他点权和，计入贡献。

然后我们考虑环上怎么处理。对于每一个点，有两种情况：断掉 $u$ 到环上前驱 $v$ 的边，使环变成一个链；或者是断掉 $v$ 的重儿子，维护当前形态。

分讨转移即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-06 19:13:00

本题就是在基环树上找直径。

我们可以先找出不带环时的直径。因为边权非负，我们可以用两次 DFS 或者树形 DP。

然后考虑带环的时候，直径会怎么变化。由于只有一个环，直径一定分为两个部分：树边组成的与环上的，设它们的交界点为 $p$ 与 $q$，那么总直径长为 $f(p) + f(q) + \sigma(p,q)$。

但是，找这个最大值同样是无法接受的，这才是本题的难点。我们将环拆成两倍长度的链，于是问题转化成：在这个链上找 $f(i) + f(j) + \sigma(i, j)$ 的最大值，$\text{s.t.} \space \lvert j - i + 1\rvert \le n$。

这可以用单调队列。以上。

好题！