CSP/NOIP 篇

[TOC]

$\downarrow 2023.07.18$

有一道原题，有点难受。所以 300。

出题人也是真厉害……不说了。

下发的题解非常的弱智，有很多地方几乎是错的……太难受了。

所以决定写这篇。

gnsi

（其实是sign，绝+1）

重心有一个结论：三点 $\to$（横坐标的平均值，纵坐标的平均值）

所以可以很轻易的找到上下界来判断。

quencese

傻逼计数

考虑递推的式子，设 $f_{t, i}$ 表示第 $t$ 次最后一个数是 $i$ 的可能数：

$$f_{t, i} = \sum_{j = 1}^{\lfloor \sqrt i \rfloor} f_{t + 1, i} $$

又由于实际上 $t$ 据说在 $10$ 次左右就只剩下了 $1$，也就是说，$\forall (t_1, t_2) (f_{t_1, i} = f_{t_2, i})$。

所以只保留 $i$ 这一维，向上推即可。

这是 $O(n \sqrt n)$ 的，显然不够优秀，所以考虑优化。

看式子，长得像前缀和，于是利用前缀和优化：

设 $g_i = \sum_{j = 1}^{i} f_j$。

于是有 $f_i = g_{\lfloor \sqrt i \rfloor}$。

两者稍微合并一下：

$$g_i = sum_{j = 1}^{i} g_{\lfloor \sqrt j \rfloor} $$

很明显，这里可以用类似数论分块的方法求和即可。

大概的复杂度是：

$$T(n) = \sqrt n T(\sqrt n) + O(\sqrt n) $$

但是显然这个式子不太对，应该有一个类似积分的东西。复杂度为 $O(n^{\frac 34})$

这是核心代码：

using lint = long long;
lint calc(lint x) {
    if (g.get(x))
        return g.get(x);
    if (x == 1) return 1;

    lint v = 0;
    for (lint i = 1; i * i <= x; ++i) {
        lint r = min(x + 1, (i + 1) * (i + 1));
        v += calc(i) * (r - i * i) % mod;
        v %= mod;
    }

    g.set(x, v);
    return v;
}

trolcon

弱智 DP 题，根本做不来。

很明显的结论是最多只需要合并三次，所以考虑用合并的次数作为状态之一，找到最小的支配集大小：

设 $f_{i, k}$ 表示考虑到第 $i$ 个线段，合并的 $k$ 次时，最小的支配集大小。

定义 $last_i$ 表示第 $i$ 条线段左侧右端点最大的线段（不相交）。

$conj_i$ 表示与第 $i$ 条线段相交的线段中左端点最小的线段。$conj^k_i$ 就是嵌套几层下去……

于是可以有转移方程：

$$f_{i, k} = \min{ f_{last_i, k} + 1, \min_{t = 0}^{k} (f_{conj^{t + 1}_i, k - t} + 1}) $$

看着头皮发麻 QwQ

那么问题在于如何维护 $last_i$ 和 $conj_i$……这可以用 set 进行维护。

考虑根据当前考虑的区间的左端点分成三个部分：完全在左边（按照右端点排序），包含了左端点（按照左端点排序），完全在右边。

然后类似于单调栈的思路不断弹出即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>

using namespace std;
const int N = 1e5 + 7;

struct LR {
    int l, r, i;
} segs[N];

struct cmpByR {
    bool operator() (const LR &lhs, const LR &rhs) {
        return lhs.r > rhs.r;
    }
}; 

struct cmpByL {
    bool operator() (const LR &lhs, const LR &rhs) {
        return lhs.l < rhs.l;
    }
};

set<LR, cmpByL> all, rs, ms;
set<LR, cmpByR> ls;

const int M = N * 30, INF = 1e9 + 7;

int last[N], conj[N];
int f[N][4];

int main() {
    freopen("trolcon.in", "r", stdin);
    freopen("trolcon.out", "w", stdout);

    cin.tie(0)->sync_with_stdio(false);

    int n; cin >> n;
    for (int l, r, i = 1; i <= n; ++i) {
        cin >> l >> r;
        all.insert({l, r, i});
        rs.insert({l, r, i});
    }

    int maxk = 0, ending = 1;
    for (auto it : all) {
        int x = it.l;
        while (!ms.empty() && ms.begin()->r < x) {
            ls.insert(*ms.begin());
            ms.erase(ms.begin());
        }

        while (!rs.empty() && rs.begin()->l <= x) {
            ms.insert(*rs.begin());
            rs.erase(rs.begin());
        }

        int i = ending = it.i, lst = ls.size() ? ls.begin()->i : 0, cont = ms.size() ? ms.begin()->i : 0;
        last[i] = lst, conj[i] = cont;
        for (int t = 0; t <= 3; ++t) {
            f[i][t] = f[lst][t] + 1;
            for (int k = 0, con = cont; k <= t; ++k, con = conj[con]) {
                f[i][t] = min(f[i][t], f[last[con]][t - k] + 1);
            }

            maxk = max(maxk, f[i][t]);
        }
    }

    if (maxk <= 1)
        return cout << "-1" << '\n', 0;
    for (int k = 1; k <= 3; ++k) {
        if (f[ending][k] < f[ending][0]) {
            cout << k << '\n';
            return 0;
        }
    }

    cout << "ROCKYOU" << '\n';
    return 0;
}

doog

利用矩阵有结合律以及没有交换律，以及矩阵的逆的性质即可。

$\downarrow 2023.08.21$

casio 卡西欧

多组询问，求不小于 $n$ 的最小的质数，或者最小质因数严格大于固定的 $p$ 的数。

$n \le 3e7, T \le 1e5, p \le 1e9$。

$O(n)$ 线性筛，然后二分即可。注意第二部分可能为空（因此痛失 AK）

jump 跳跃

对于给定数列，$A_0 = \infty$，找到 $A_i$ 前第一个比它大的数。

利用单调栈即可 $O(n)$。

lca 最近公共祖先

求 $\sum_{i = 1}^n \sum_{j = 1}^n lca(i, j)$，其中 $lca(i, j)$ 表示点 $i$ 和 $j$ 的最近公共祖先编号。

• 将 $lca(i, i)$ 摘出来，考虑记忆化 DSF 即可

• 考虑换根即可

excellent 优秀的拆分

存在可变字符，求 $AABB$ 划分的方案数。

$n \le 3000$。

类似 NOI 优秀的拆分，考虑枚举 $len$，撒点，找 $LCS$ 和 $LCP$。

由于存在可变字符，只能 $O(n)$ 找 $LCS$ 和 $LCP$。

可以差分得到 $f_i, g_i$ 分别表示以 $i$ 开始或结束形如 $AA$ 的划分可能数。

于是有 $\sum_{i = 2}^n f_i g_{i - 1}$

所以总复杂度 $O(n^2)$。

$\downarrow 2023.08.23$

flip 翻转

给定长度为 $2n - 1$ 的 $10101\cdots01$ 串，每一次只能翻转连续的 $1010\cdots$ 串，并且只能以 $1$ 开头，结尾，求翻转 $k$ 次的方案数。

傻逼题。。考虑操作的区间要么相离，要么相交，并且后面的一定被前面的覆盖。所以考虑先构造操作区间关系，然后还原位置。套路？

新加入第 $i$ 个区间会把一个区间分成三段（也就是增加了两段）所以有 $2i - 1$ 种插法。

于是一共有 $\prod_{i = 1}^k (2i - 1)$ 种相对关系。

每一种相对关系最多只需要 $k$ 个 $1$ 即可构造出最小的可行串，所以考虑补充 $1$ 的个数到 $n$。

于是考虑插板，有 ${(n - k) + (2k + 1) - 1 \choose n - k} = {n + k \choose n - k}$ 种插法。

所以一共有 ${n + k \choose n - k}\prod_{i = 1}^k (2i - 1)$ 种方案。

……我太傻比了，当时想了一个 $O(n^6)$ 的递推式子：

$$f_{n, k} = \sum_{i = 1}^n \sum_{j = i}^n \sum_{x = 0}^{k - 1} $$

\sum_{y = 0}^{k - 1 - x}
f_{i - 1, x} \times f_{j - i, y} \times f_{n - j, k - 1 - x - y}
\times {k \choose x}{k - x \choose y}

$$ 然后，就原地升天 QwQ $$

lint f(int n, int k) {
    lint r = C(n + k, n - k);
    for (int i = 1; i <= k; ++i) r = r * (2 * i - 1) % mod;
    return r;
}

$\downarrow 2023.08.24$

travel 环游世界

给定一些区间异或和，限制值域为 $[0, 2^k)$，求合法序列个数。

考虑转化为异或前缀和上点对的贡献。

可以转化为一张图，求连通块个数，每一个连通块都有 $2^k$ 种取法。

但是可能有冲突，可以考虑 $O(n + m)$ 跑一次，合法的充要条件为两点之间任意路径异或和权值相等。

可以考虑随机确定一个点，dfs 判断即可。

elevator 载客电梯

一个人的等待时间定义为从开始到他坐电梯到一楼经过的时间，有 $n$ 个人，电梯限载 $k$ 人。

求最短等待时间。

有式子：

$$f_{i} = \min_{i - k \le j \lt i} f_j + 2v_i(n - j) $$

类似于斜率优化。考虑到 $v_i$ 递增（必要条件），于是考虑李超线段树。

只是不是维护整数上，而是维护 $v$ 序列上的最值，下标也限定值域，复杂度 $O(n \log^2 k)$。

感谢 lca（来自 UOJ 群的大佬）给出的另一个做法。

考虑将序列分成 $\frac nk$ 块，块大小为 $k$。

维护当前块的前缀凸包，维护前一个块的后缀凸包（可支持撤销）。这使得均摊 $O(1)$。

于是两个凸包上可以二分寻找答案，使得总复杂度为 $O(n \log k)$。

$\downarrow 2023.08.25$

yo 十一之争

给定一个长度为 $n$ 的数字串 $s$ 和只包含 yo 的字符串 $t$，yoimiya 会和 oimiya 玩 $n$ 轮游戏，初始有一个数字串 $x$ 为 $0$ ，每次：

• 如果 $t_i$ 是 $y$ 则是 yoimiya 操作，如果是 $o$ 则是 oimiya 操作。

• 每次操作：将 $s_i$ 或者 $0$ 加入 $x$ 的末尾。

如果最后 $x$ 是 11 的倍数，那么 yoimiya 获胜，否则 oimiya 获胜。

考虑记忆化搜索，令 dfs(i, x) 表示当前在第 $i$ 轮，当前余数为 $x$，yoimiya 是否可能获胜。

如果是 yoimiya 操作，那么如果下一轮的可能中有可以胜利的状态，那么当前 y 可以胜利。

如果是 oimiya 操作，如果下一轮的可能中有使得 yoimiya 失败的状态，那么当前 y 不可以胜利。

博弈论，必胜态和必败态之间的转换，MEX 的利用，可以体现在这其中。

适合博弈小白（我，考场上做不来。

double 双倍经验

两棵形状相同的树，对应点有连边。求两颗树上两点间的最短距离。

好歹还是花了 3h 写出来 QwQ

考虑每一次 $O(n)$ 的 DP。先把链拆出来，有：

$$f_{x, 0} = \min(f_{y, 0} + w_0, f_{y, 1} + w_1 + c_x) \\ f_{x, 1} = \min(f_{y, 1} + w_1, f_{y, 0} + w_0 + c_x) $$

于是可以写成广义矩阵的形式：

$$\begin{pmatrix} f_{x, 0} & f_{x, 1} \end{pmatrix} = \begin{pmatrix} f_{y, 0} & f_{y, 1} \end{pmatrix} \begin{pmatrix} w_0 & w_1 + c_x \\ w_0 + c_x & w_1 \end{pmatrix} $$

于是考虑维护每一个点到父节点的矩阵。

查询的时候找 LCA，然后树链剖分加线段树维护矩阵乘积即可。

复杂度为 $O(n + q \log^2 n)$。

---

NOTICE：有一种情况会出错：

但是考虑到要么从上面一条边转过来，要么从下面一条边转过来。

所以需要上下扫一遍，但是考虑需要先向上后向下。考虑如下情况：

---

现在考虑优化。

为什么需要树链剖分呢？好傻逼啊我。

利用倍增的同时维护路径信息：f[x][k][0/1][0/1] 表示从 $x$ 开始向上跳 $2^k$ 步，初始在 $0/1$ 边，结束在 $0/1$ 边的最短路径。枚举中间状态合并即可。

于是复杂度变为：$O(n \log n + q \log n)$

---

来自 SWC 的想法

考虑一般 $O(n^2)$ 状态 $O(n)$ 算的优化方法：分治，左边右边分别处理，然后超级合并。

于是本题可以考虑类似的想法：点分治。

一对点可以被其路径上的任意一个点作为分割点，然后合并。

点分治保证了每一个点都作为了一次分割点，并且两端覆盖到了每一条链。

于是可以做到复杂度 $O(n \log n + q)$，于是考虑加强数据 QwQ

permution 排列变换

定义两个排列 $p, q$ 的加法的结果为使 $ans_{p_i} = q_i$ 的排列。

已知 $f_0 = p, f_1 = q, f_n = f_{n - 2} + f_{n - 1}$ 求 $f_k$。

---

这个鬼加法没有一点好的性质。但是万幸的是 $f_k$ 有一个良好的性质可以供我们写暴力，也就是循环节：$\exists loop \forall i \ge loop f_i = f_{i - loop}$。

于是可以写 $O(n \times loop)$ 暴力了……

---

关于排列相加，可以写成置换的形式：

$$p + q = \begin{pmatrix} p_1 & p_2 & \cdots & p_n \\ q_1 & q_2 & \cdots & q_n \\ \end{pmatrix} $$

显然上方无序，考虑变成有序：

$$p(p + q) = \begin{pmatrix} 1 & 2 & \cdots & n \\ p_1 & p_2 & \cdots & p_n \\ \end{pmatrix} \begin{pmatrix} p_1 & p_2 & \cdots & p_n \\ q_1 & q_2 & \cdots & q_n \\ \end{pmatrix} = \begin{pmatrix} 1 & 2 & \cdots & n \\ q_1 & q_2 & \cdots & q_n \\ \end{pmatrix} = q $$

于是可以有：

$$p + q = p^{-1}q $$

于是考虑打表找 $f_k$ 的规律，便可以发现：

$$\begin{aligned} f_0 &= p \\ f_1 &= q \\ f_2 &= p^{-1}q \\ f_3 &= q^{-1}p^{-1}q \\ f_4 &= q^{-1}pq^{-1}p^{-1}q \\ f_5 &= q^{-1}pqq^{-1}pq^{-1}p^{-1}q = q^{-1}ppq^{-1}p^{-1}q \\ f_6 &= q^{-1}pqp^{-1}qq^{-1}ppq^{-1}p^{-1}q = q^{-1}pqpq^{-1}p^{-1}q \\ f_7 &= q^{-1}pqp^{-1}p^{-1}qq^{-1}pqpq^{-1}p^{-1}q = \underline{q^{-1}pqp^{-1}}q\underline{pq^{-1}p^{-1}q} \\ f_8 &= q^{-1}pqp^{-1}q^{-1}p^{-1}qq^{-1}pqp^{-1}qpq^{-1}p^{-1}q = \underline{q^{-1}pqp^{-1}}p^{-1}q\underline{pq^{-1}p^{-1}q} \\ \vdots \end{aligned} $$

令 $g = q^{-1}pqp^{-1}$，那么可以发现：

$$f_n = g f_{n - 6} g^{-1} (n \ge 6) $$

于是得出：

$$f_n = g^{\lfloor \frac n6 \rfloor} f_{n \bmod 6} g^{-\lfloor \frac n6 \rfloor} $$

快速幂即可（考虑置换的性质，满足结合律，但是不满足交换律）

stone 石头游戏

$n$ 堆石头，每一次可以选择一堆 $a_i = i$ 的石头，全部去掉，但是将 $1 \sim i - 1$ 的石头堆全部加一个。定义失败度为剩下石头的个数。

对于每一种限制在 $a_i \le k$ 的方案，求最小化的失败度之和。答案 $\bmod 1e9 + 7$。

最优策略一定是每一次找最左侧可以操作的石堆，立即操作。

可以发现这东西对于后面的石堆没有影响。所以考虑把后面对前面的影响作为状态进行 DP。

令 $f_{i, j, l}$ 表示在 $i$ 位初始放 $j$ 影响的前面 $l$ 次的答案之和，$g...$ 表示方案数。

于是有：

$$f_{i + 1, j, l} \to f_{i, (x + l) \bmod i, l + \lfloor \frac {x+ l}i \rfloor} (x \le i) \\ f_{i + 1, j, l} \to f_{i, x + l, l} (x \gt i) $$

但是发现，似乎 $j$ 并没有什么用，于是考虑压掉。

也就是：

$$f_{i, l + \lfloor \frac {x+l}i \rfloor} \leftarrow f_{i + 1, l} $$

于是便搞定了。

f[n + 1][0] = 0, g[n + 1][0] = 1;
int V = 0;
for (int i = n; i; --i) {
    for (int j = 0; j <= V; ++j) if (g[i + 1][j]) {
        for (int x = 0; x <= k; ++x) {
            int add = 0, ret = (x + j);
            if (x <= i) add = ret / i, ret %= i;
            (g[i][j + add] += g[i + 1][j]) %= mod;
            (f[i][j + add] += (f[i + 1][j] + 1ll * ret * g[i + 1][j]) % mod) %= mod;
            V = max(V, j + add);
        }
    }
}

$\downarrow 2023.08.26$

graph

有偏序关系 $(x_i, y_i) \le (x_j, y_j) \iff x_i \le x_j, y_i \le y_j$。

给出很多对元素，求偏序图上的连通块数量。

首先按照横坐标为第一关键字，纵坐标为第二关键字排序。

一种是可以证明连通块一定是一个区间。

找到每一个点最左最右的连通点即可。

一种是先利用单调栈找到右上角的点，然后两两合并即可。

三是题解的做法，只利用单调栈，非常优秀。

car

Codeforces 581E

目前有三种做法：

• 题解做法

• 线段树做法

• 我的做法

题解的做法非常巧妙，依次假设没有不优秀的东西缺失的零食个数。于是可以每一次 DP 做。最后二分找出下一个超市，判断即可。

线段树做法有一步巧妙的转换。在每一个商店后面染色，但是有优先度。所以可以考虑区间取 $\min$。然后维护区间 $0/1/2$ 的个数即可。

我的做法类似于一个 DP 转移。也就是考虑一个三元组，从后继转移即可。

robot

explorer

超级计数题。

可以转换位如图 5 种关系。其中只有两种关系符合要求。

但是考虑这两种关系不好计数。所以考虑容斥。

蓝色定义为左边的线，红色定义为右边的线。

左边的线满足：

$$a, b \lt x \\ $$

a, b \gt y \
a \le x \text{ and } b \gt y

$$ 右边的线满足： $$

x \lt a \lt b \lt y

$$ 于是变成了偏序问题，树状数组维护即可。 $$

如何计数？

Type1 可以为：$\sum_{i = 1}^n l_i r_i$。

Type 3，4 可以归为两线不相交，但是有两线相交，可以先选出不相交的，再选出相交的。但是这样会重复计算两次，所以考虑 $\frac 12$：$\sum_{i = 1}^n (l_i + r_1)(n - 1 - l_1 - r_1)$。

最终用 $n \choose 3$ 减去上者即可。

$\downarrow 2023.08.28$

increase 递增路径

Alice 和 Bob 轮流操作（Alice 先手），走边权严格递增的路。

Alice 希望多走，Bob 希望少走。

保证边权互不相等。最优的情况下，求出对于每一个起点的轮数。

• 对于边的记忆化，是 $O(m)$ 但是常数比较大。

void dfs(int x, Edge &e) {
    if (~e.alice) return ;
    int pw = e.w;

    int ali = -1, bob = N;
    for (auto &e : G[x]) {
        if (e.w <= pw) continue;
        dfs(e.to, e);

        bob = min(bob, e.alice + 1);
        ali = max(ali, e.bob + 1);
    }

    if (ali == -1) ali = bob = 0;
    e.alice = ali, e.bob = bob;
}

• 或者考虑按照边权逆序加边，类似 $\uparrow 2023.08.24$ journey 一题，$O(m)$。

ring 环上排列

对于一个排列（形成一个环），按照值顺序，交换值两侧的值。

如果存在第 $i$ 次交换，两侧的值 $x \lt i \lt y$，那么排列合法。

计数合法排列的数量。

考虑容斥，计数不合法序列。

设当前值为 $i$，依据题意，$\lt i$ 的值一定被操作过，而 $\gt i$ 的值一定没有被操作。

若给操作过的中心数染色，不合法的操作满足两侧的颜色相同。

打表观察可知，排列与操作序列一一对应，于是计数不合法的操作序列。

不难知偶数序列一定不存在不合法序列，所以只需要计数奇数序列。

考虑递推，设 $f_n$ 表示对于长度为 $2n - 1$ 的序列合法操作的数量。枚举下一个分割的点，有：

$$f_n = \sum_{i = 1}^{n - 1} {2n - 2 \choose 2i - 1} f_i f_{n - i} $$

考虑系数，也就是两边的两个排列合并，值可以插，为 $2i - 1 + 2(n - i) - 1 -1 \choose 2i - 1$ 也就如 $\uparrow$。

于是最终的答案为 $n! - n \times f_{\frac n2}[\text{n is odd]}$。

mex 求和

给定序列 $B$，对于满足 $\forall i, 0 \le A_i \le B_i$ 的所有序列 $A$，求 $\sum \mathrm{mex}(A)$。

先考虑枚举 $\mathrm{mex}$，然后对此 DP。

有一个很 naive 的 $O(n^2)$ 做法：

$$\begin{aligned} f_{i, l} = &f_{i - 1, l} \times [\min(v_i + 1, l), \max(v_i - l, 0)] + \\ & f_{i - 1, l - 1} \times [\min(\mathrm{mex}, v_i + 1) - l + 1] \end{aligned} $$

于是总复杂度为 $O(n^3)$。

考虑优化，重复利用信息（套路来自 SWC）。

将序列分为两部分：

左边可以进行一次 DP，右边再一次 DP。

左边的话由于可以看作 $\mathrm{mex}$ 极大，所以有转移：

$$f_{i, j} = f_{i - 1, j} \times j + f_{i - 1, j - 1} \times (v_i + 1 - (j - 1)) $$

右边的话 $g_{i, j}$ 表示选择在后面补充 $j$ 个值。

由于顺着不好 DP，所以考虑逆着。

有：

$$g_{i, j} = g_{i + 1, j - 1} \times j + g_{i + 1, j} \times (v_i + 1 - (j + 1)) $$

也就是要么不上前面缺失的 $j$ 个数之一，要么不补前面缺失的数，并且也不补此时的 $\mathrm{mex}$。

于是对于每一个 $\mathrm{mex}$，找到分界，答案为 $\sum_{i = 0}^n f_{x, i}g_{x + 1, \mathrm{mex} - i}$。

centroid 从 LCA 到重心

首先考虑重心的性质：其所在子树大小不小于 $\frac {n + 1}2$。

所以其 $dfn$ 一定在 $[1, \frac {n+1}2]$ 中。

根据评分发现，询问次数应该在 $O(\log n)$。所以应该是二分。

于是考察某一个单调性。令 $g = \frac {n + 1} 2$，令当前询问为 $x$。

若 $lca(x, g) = lca(x, x + g - 1)$，那么 $x$ 小了。

正确性可以考虑分类讨论，所以可以倍增/二分。

$\downarrow 2023.08.29$

ak AK 神

$n$ 堆石头，两个人轮流操作，每次可以选择连续的 $k$ 堆石头，将它们拿走，剩下的石头合并成一个新的石头序列，直到剩下唯一一堆石头时结束。

Alice 先手，想要拿走总和最小，Bob 后手，想要拿走总和最大。

策略最优，求拿走的总和。

保证 $n \equiv 1 \pmod k$。

考虑有事实只有 $i \equiv 1 \pmod k$ 的位置的值最终才可能被保留。

也就是两人都知道了每一次只能拿走一个有用的数。

所以最优下剩下的是中位数。拿出来排序即可。

注意 $k = 1$ 的特殊情况。

au 金牌爷

很离谱的计数题。

首先考虑枚举第二层的个数 $i \ge \lfloor \frac n2 \rfloor$，一共可以选出 $n \choose i$ 个数填入（由于是树，所以没有本质区别），然后考虑剩下的点连上去，一共有 $i^{n - i - 1}$ 中接法，但是其中可能有部分不合法。

所以考虑容斥掉，考虑到第三点限制中，最多只有一个子树可以满足 $\gt \lfloor \frac n4 \rfloor$。也就是说有 $\ge \lfloor \frac n4 \rfloor$ 个点连到同一个子树就会不合法。考虑连的数量 $j$，可以选出 $n - i - 1 \choose j$ 个连上，可以连 $i$ 种。剩下的点可以在剩下的点里随便连，所以有 $(i - 1)^{n - i - 1- j}$ 种连法。

于是不合法的数量也就是

$$\sum_{j = \lfloor \frac n4 \rfloor}^{n - i - 1} i \times {n - i - 1 \choose j} \times (i - 1)^{n - i - 1 - j} $$

所以复杂度，$O(n^2)$。

只是需要特判 $n = 1, 2$ 的情况！

king 原题哥

给定 $n + m$ 个物品，$n$ 个物品可以花费 $1$ 得到 $c$ 的价值，$m$ 个物品既可以花费 $1$ 得到 $a$，也可以花费 $2$ 得到代价 $b$。求至多花费 $v$ 可以得到的最大价值。

骗分做法：

先考虑贪心，也就是把每一个花费的价值最大化。

但是在 $v$ 比较小的时候会出现 $(1), (100), (1, 101)$ 的情况把这个给卡掉。

所以在 $v$ 比较小的时候暴力背包一下即可。

正解：

• 做法1：还是类似的贪心，若 $a \ge b - a$，那么就可以维护当前可选集合贪心，因为不可以跳过 $1$ 代价直接选择 $2$ 代价。所以如果选完 $B$ 的 $1$ 代价，将 $b - a$ 看成新的 $1$ 代价加进去即可。

  对于 $a \lt b - a$，可以证明不会有超过两个 $B$ 选了 $1$ 代价。

  也就是可以枚举选择一个 $1$ 代价，其余排序后是一个前缀。所以考虑枚举前缀，选择 $b - a$ 最小的，否则是 $a$ 最大的即可。

• 做法2：类似状态转移，每次增加 $1$ 的代价。

  将每一个物品看作三种状态，$0/1/2$ 表示花费的代价。

  于是会有四种最优决策：

  • $0 \to 1$，选择新的一个

  • $1 \to 2$，选择额外的一个

  • $1 \to 0, 0 \to 2$，扔一个，再取一个 $2$。

  • $2 \to 1, 0 \to 2$，降一个，再取一个 $2$。

  于是暴力维护即可。

复杂度 $O(n \log n)$。

loser 弟中弟

树上每个点上有一个左括号或右括号，带修改（翻转某个区间），求 $x \to y$ 的简单路径上最长的合法括号序列长度。

树链剖分加线段树维护括号信息即可。

在修改的部分，需要交换正逆信息，合并查询即可。

复杂度 $O(n \log^2 n)$。

$\downarrow 2023.08.30$

tsuki 月华

对于一个矩阵，多次询问子矩阵乘积，模数为任意正整数。

$n, m \le 10^3, q \le 2 \times 10^6$

如果常数够小，那么 $O(nm \log n \log m + q \log n \log m)$ 是可以过的，$4 \times 10^8$ 也不多。

所以考虑倍增，类似支持区间加的 Spare Table。

但是空间太大了，需要 412MB 左右。但还是过了。

所以考虑正解。

将 $mod$ 质因数分解后对于每一个质因子用二维前缀和记录出现次数，剩下的用 exgcd 求逆元即可。

light 万分之一的光

一棵树，每次选择一个未选择的点，得到贡献 $a_i$，并令周围的点 $a_j = a_j + a_i$。最大化贡献。

想不到，根本想不到。

树上背包，模型转化为一个点可以到 $j$ 个点，那么贡献为 $j \times a_x$。

令 $f_{x, i}$ 表示 $x$ 的父边定向到父亲，可以到达 $i$ 个点，$g_{x, i}$ 表示父边定向到自己，可以到达 $i$ 个点。

所以考虑树上背包，令 $h_{x, s, t}$ 表示 $x$ 总可以到达 $s$ 个点，在子树内可以到达 $t$ 个点。

于是合并背包时有：

$$h_{x, s, t}' = \max (h_{x, s, t} + f_{y, s}, \max_{k} (h_{x, s, t - k} + g_{y, k})) $$

合并完之后：

$$g_{x, t} = \max(h_{x, s, t} + s \times a_x) \\ f_{x, t - k - 1} = \max_k h_{x, s, k} + s \times a_x $$

于是就可以写出来了。

考虑细节很多，核心如下：

void dfs(int x, int p) {
    for (int y : G[x]) {
        if (y ^ p) dfs(y, x);
    }

    for (int s = 1; s <= n; ++s) {
        siz[x] = h[0] = 0;
        for (int y : G[x]) {
            if (y == p) continue;

            for (int i = 0; i <= siz[x]; ++i) {
                chmax(t[i], h[i] + f[y][s]);
                for (int j = 0; j <= siz[y]; ++j)
                    chmax(t[i + j], h[i] + g[y][j]);
            }

            siz[x] += siz[y];

            swap(h, t);
            fill_n(t, n + 1, -inf);
        }

        for (int k = 0; k <= s - 1 && k <= siz[x]; ++k)
            chmax(f[x][s - k - 1], h[k] + 1ll * s * v[x]);
        chmax(g[x][s], h[s - 1] + 1ll * s * v[x]);
    } ++siz[x];
}

$\downarrow 2023.09.01$

poly 多项式

已知 $x + y$ 和 $xy$，求 $x^n + y^n$，对于质数取模。

两种做法：

• 矩阵快速幂递推：$x^{n + 1} + y^{n + 1} = (x^n + y^n)(x + y) - xy (x^{n - 1} + y^{n - 1})$

• 记忆化搜索：$x^{2n} + y^{2n} = (x^n + y^n)^2 - 2(xy)^n$，以及 $x^{2n + 1} + y^{2n + 1} = (x^n + y^n)(x^{n + 1} + y^{n + 1}) - (x + y)(xy)^n$。

reverse 平衡树

每次翻转区间 $[1, a_i]$，保证 $a_i$ 递增。

可以发现会构成 $m$ 个整体，从最后一个向前，隔一个放在最前面，并且反转，剩下的依次放即可。

fight 聚众斗殴

$n = 2^k$，给定长度为 $n - 1$ 的数组，将 $x$ 插入任意位置，每次进行如下操作，求 $x$ 剩下的概率。

• 取出前两个数 $x, y$

• $\frac {x}{x + y}$ 几率保留 $x$，$\frac y {x + y}$ 几率保留 $y$，将保留的加到最后。

不难发现相当于两两合并。所以考虑记忆化搜索即可。

cactus 喀克托斯

仙人掌 DAG 拓扑序计数。

$O(n^2)$ DP.

$\downarrow 2023.09.03$

steiner 斯坦娜

对于一张无向图，对于所有的 $x > 2$，求 $\{1, 2, x\}$ 的最小联通距离。

考虑只有两种情况：

$$x \to y \to z $$

或者

$$x \to m \to z \\ \downarrow \\ y $$

$3$ 次 DJK 即可。

count 数数

给定 $n, m$，需要构造 $m$ 个非空集合 $A_1, A_2, \cdots, A_m$，使得 $\bigcup_{i = 1}^m A_i = \{1, 2, \cdots, n\}$，求多少种构造方案。

相当于在 $n \times m$ 的矩阵中染色，使得每一列和每一行都有被染色的格子。所以可以 $\mathrm{swap}(x, y)$。

考虑二项式反演，所以可以得到式子：

$$\sum_{i = 1}^m (-1)^{m - i} {m \choose i} (2^i - 1)^n $$

perm 排列之美

给定序列 $A$，保证 $A_i$ 互不相等并且 $\forall i, A_i \in [1, n]$，求一个 $n$ 排列满足：

• $A$ 是字典序最小的长度为 $m$ 的序列。

考虑在 $x < A_i$ 只能放在 $A_{i - 1}$ 之前，所以考虑一一加入，记录当前有多少个元素，插入即可。

ttk 婷婷可爱

考虑建出 kruskal 重构树，在树上 $DP$ 即可。

有一个常见的树上背包的优化，把 $O(n)$ 给去掉。

也就是利用 dfn 序变成序列上 DP 即可。

所以最终的复杂度为 $O(mk)$。

$\downarrow 2023.09.05$

up 上上上

有函数：

$$f(x, i) = \begin{cases} x \bmod a_n & i = n \\ (x \bmod a_i) + f(x \bmod a_i, i + 1) & i \lt n \end{cases} $$

保证 $x \ge 0$，最大化 $f(x, 1)$。

考虑发现答案的每一段一定是一个一次函数，考虑把答案看作 $x \times n + y$ 的形式。

于是考虑利用函数更新，初始化 $(a_1 - 1, 0)$。

每次更新有三种方式：

$$\begin{aligned} (x, y) &\to (x, y) & x < a_i \\ (x, y) &\to (y + (x \bmod a_i) + (j - j \bmod a_i)) \times (i - 1) & x \ge a_i \\ (x, y) &\to (y + (i - 1) \times (\frac {(j + 1)} {a_i} \times a_i - a_i)) & x \ge a_i \\ \end{aligned} $$

然后，就没有然后了。

family 家人

$2 \times n$ 的矩阵，一些不能走，求两点的最短路。

2023.08.25 double 弱化版。

然而因为编译的问题挂了。

具体在于

int t = lg[y - x + 1];
mat r = dis[t][x]; x += lsh(t);
// assert(t != -1);
for (int i = t; ~i; --i) {
    if (x + lsh(i) - 1 <= y) 
        r = merge(r, dis[i][x]), x += lsh(i);
}

中的 ~i 一句。在此处，可以保证 $t \ge 0$，但是在 assert 时却出现了在 for 前 t == -1 的情况。导致循环炸掉 QwQ

我不认为这有办法避免……

ll 你所热爱的就是你的生活

$n \le 40$ 个物品，求总价值小于 $M \le 1e18$ 的方案数。

考虑分成两个 $20$ 状压，然后 sort 合并即可。

izumi 泉

$n \le 1e5$ 种漫画，每种在 $[l_i, r_i]$ 上都有一本。求所有每一种漫画都有奇数本的区间的长度和。

推一个式子可以发现如果 $[i, j]$ 合法，一定满足：

L[i - 1] ^ sum[i - 1] ^ R[j] ^ sum[j]

但是需要排除一个都没有的区间。

考虑利用 map $O(n \log n)$ 做即可。

// 构造差分序列 
for (int l, r, i = 1; i <= n; ++i) {
    cin >> l >> r;
    sum[l] ^= ha[i], sum[r + 1] ^= ha[i];
    L[r] ^= ha[i], R[l] ^= ha[i];
}

for (int i = 1; i <= m; ++i) L[i] ^= L[i - 1];
for (int i = 1; i <= m; ++i) R[i] ^= R[i - 1];

// 前缀和一次变成原序列 
for (int i = 1; i <= m; ++i) sum[i] ^= sum[i - 1];
// 前缀和两次变成前缀和 
for (int i = 1; i <= m; ++i) sum[i] ^= sum[i - 1];

更好的做法：

将漫画摆放区间和选择区间的左侧或右侧去掉一个，可以发现区间中存在的每一种漫画都恰好去掉了一个。

所以只需要 sum 求即可。

注意：两种方法都需要减去一个都没有的区间。

$\downarrow 2023.09.07$

T1

给定两个⻓度为 $n \le 1e6$ 的序列 $a$ 和 $b$，序列 $c$ 需要满足：⻓度为 $n$，且 $c_i$ 为 $a_i$ 或 $b_i$。
询问在所有可能的序列 $c$ 中，最⻓严格上升子序列的⻓度。

类似一般的最长上升子序列，离散化后树状数组即可。

T2

给定 $n \le 1e5$，$m \le 1e6$ 次操作，操作如：

1. 加入随从 $h$，保证 $1 \le h \le n$。

2. 给定 $[l, r]$，攻击系数随机其中，询问期望攻击次数 $\times (r - l + 1)$。

攻击次数有规则若有随从血量 $\le 0$，则继续，否则停止。

首先不难发现答案最大为 $\frac n1 + \frac n2 + \dots + \frac n n = O(n \log n)$

先考虑一个在线算法 $O((n + m) \log^2n)$。

假定每一个系数 $d$ 的答案更新到 $k$，于是会影响他的 $h$ 所在的区间 $(dk, dk + d]$。

考虑类似标记永久化的线段树标记，内部用 set 维护，每次查删即可。

一般需要 3s，很难。

其次考虑另一个算法 $O(n \sqrt n + n \log^2n + m \log n)$。

考虑每一个 $h$ 最多影响 $O(\sqrt n)$ 个系数对应的区间，所以考虑暴力标记，如果标记了则可以暴力跳。

而标记为了保证只标记 $O(n \log n)$ 次，所以需要利用类似于并查集的做法维护即可。

一般要 1.2s，烦。

考虑离线做法，考虑每一个 $d$ 被更新的时间，以及次数。

在查询的时候重新加入即可，为 $O(n \log n + n \log^2 n + m \log n)$。

可以过……牛逼 YnOI

T3

首先有一个 $O(n^3 \log n)$ 的做法，问题不大。

考虑一个斜率什么时候会影响两点的顺序，也就是为其垂线的时候。

所以可以把所有的为正的垂线斜率取出来一一判断。

由此可以证明出，合法的斜率一定在其中出现过，如果没有，那么一定不合法。考虑如果存在一个斜率合法，那么稍稍调整到最近的出现过的斜率并不会影响到任何点对的相对顺序，所以得证。

然后考虑 $O(n^2 \log n)$，对斜率先排个序，考虑递增的斜率会有什么影响。

发现不会影响到斜率大于/小于的点对的相对顺序，所以将影响到的拿出来重新排列即可。

而且拿出来的一定是连续的一些段，考虑斜率都是和 $\frac 1k$ 最相近的，投影的位置很相近，所以是连续的。

这样维护前缀和也是简单的了。

$\downarrow 2023.09.09$

length 基环树环长

给定正整数 $k$，对于长为 $n$ 的序列 $a_i$ 表示 $i$ 向 $a_i$ 连边，其中 $a_i \in [1, n]$，求所有简单环（包括自环，二元环）环长的 $k$ 次方之和。

考虑枚举每一个环，找出其出现的序列的个数即可。发现编号十分的规律，所以枚举环长即可。

于是可以推出式子：$\sum_{i = 1}^n {n \choose i} i^k n ^{n - i} (i - 1)!$。

$i^k$ 由于积性，所以可以线性筛 $O(n + \pi(n) \log k)$ 求，$n^{n - i}$ $O(n)$扫一遍或者$O(\sqrt n)$ 光速幂预处理即可。

可以认为 $\pi(n) \sim \frac n {\log n}$

permutation 排列

一个排列时好的当 $\forall k \in [1, n)$ 有 $\sum_{i = 1}^k p_i > p_{k + 1}$，求字典序第 $r$ 下的排列 $p$。

$n \le 10^6, r \le 10^{18}$。

发现 $20! > 10^{18}$，所以当 $n$ 很大的时候只有最后二十位有用，前 $n - 20$ 位按照：$3, 1, 2, 4, 5, \cdots$ 排列，这一定是字典序最小的。

发现到 $O(\sqrt n)$ 长度之后后面无论怎么填都可以，所以 $n$ 很大可以定义为 $n \ge 27$。

所以当 $n$ 很小的时候暴力（相对）搜索即可。

void dfs(int x, int sum) {
    if (x > n) {
        if (r == 1) {
            prt(); exit(0);
        } else return ;
    }

    for (int i = 1; i < sum && i <= n; ++i) {
        if (exi[i]) continue;
        P[x] = i, exi[i] = 1;
        if (sum <= n) dfs(x + 1, sum + i);
        else if (r > fac[n - x]) r -= fac[n - x];
        else dfs(x + 1, sum + i);
        exi[i] = 0;
    }
}

raid 总力战

考虑询问离线，$O(n^2)$ 枚举直线之间的贡献，进行差分。

最后每个直线 $O(n)$ 单调栈扫一遍即可。

复杂度 $O(n^2 \log n + q \log n)$。

$\downarrow 2023.09.12$

gen 二进制

定义 $f (x, y) = (x ~\^{}~ y) × (x|y) × (x \& y)$
给你一张 $n$ 个点，$m$ 条边无向图，其中无自环，可能有重边。记点 $i$ 的度数为 $deg_i$。
请你求出 $\sum_{i = 1}^n \sum_{j = i}^n f(deg_i, deg_j)$，对于 $10^9 + 7$ 取模。

发现本质上不同的 $deg_i$ 之后 $O(\sqrt m)$ 个，所以直接上即可。

shin 字符串

给定 01 串 $S$ 和 $T$，求最小次数翻转使得 $T$ 不作为 $S$ 的子序列。

有 $|T| \le 3$。

暴力分讨即可。

但是细节很多，需要狠狠注意。

imp 计算几何

平面上 $n$ 个点 $(x, y)$，权值为 $|c| \le 10^9$，求一个对角线为 $y = x$ 的对角线的矩形，最大化其内部点的权值之和减去边长。

发现可以扁平化为一个区间 $[\min(x, y), \max(x, y)]$，于是考虑扫描线，有一个支持区间加贺区间最大值的线段树即可。

每个叶节点的初始权值为 $-app_x$。

act 博弈

给定 $n$ 个点和 $(0, 0)$，Alice 和 Bob 走到这些点就赢了（只能向左或者向下走），$q$ 次询问，每次给定起点 $(x, y)$，问谁赢。

发现 $n = 0, 1$ 的时候很 naive，考虑维护不合法的函数，以此递推。

考虑一个点会如何影响？

如果在当前一次函数的上方，那么使得函数升高一个，如果在下方，那么会降低。

考虑离线，按照横坐标第一，纵第二，问第三排序。

横坐标的影响可以预处理出来，而纵坐标的影响利用树状数组可以求出。

于是整个函数的影响都知道了，判断点是否在函数上即可。

$\downarrow 2023.09.14$

然后其实今天的题是炸的？

segtree 简单二维线段树题

原题：[Ynoi2003] 博丽灵梦 - 洛谷

greedy 简单贪心题

高楼丢鸡蛋问题，$n$ 层楼 $k$ 个鸡蛋，保证鸡蛋在 $[1, n]$ 内可以碎。

后面的性质使得可以 $--n$ 然后转为经典的原题。

在 $k$ 时发现答案为 $x$ 的区间为一个 $k$ 次多项式，其牛顿级数为：

$$f(x) = \sum_{i = 1}^k {x \choose i} $$

所以可以直接推，复杂度为 $O(\sqrt[k] n)$。

geometry 简单计算几何题

咕……傻逼题

$\downarrow 2023.09.19$

long 无尽的矩形

矩阵为：

$$\begin{bmatrix} 1 & 2 & 5 & 10 & 17 & \cdots \\ 4 & 3 & 6 & 11 & 18 & \cdots \\ 9 & 8 & 7 & 12 & 19 & \cdots \\ 16 & 15 & 14 & 12 & 20 & \cdots \\ \vdots\\ \end{bmatrix} $$

求子矩阵的和。

考虑差分即可。

而一个矩形可以分成一个正方形 + 一个小矩形：

$$[n \times n] + \begin{bmatrix} m^2 + 1 & (m + 1)^2 + 1 & \cdots & (m - 1)^2 + 1 \\ \vdots & \vdots & \ddots & \vdots \\ m^2 + n & (m + 1)^2 + n & \cdots & (m - 1)^2 + n \end{bmatrix} $$

或者：

$$[m \times m] \\ + \\ \begin{bmatrix} (m + 1)^2 & (m + 1)^2 + 1 & \cdots & (m + 1)^2 + m - 1 \\ \vdots & \vdots & \ddots & \vdots \\ n^2 & n^2 + 1 & \cdots & n^2 + m - 1 \\ \end{bmatrix} $$

然后求即可。

string 小 M 的字符串

先找出所有串，在 Trie 上排序即可。

可以做到 $O(n^2 \log n)$。

然而有个结论，存在一个一个最优解，一定没有大于 $\sqrt {2 n}$ 长度的串。

考虑每一新加入一个串，要么长度 $+1$，要么减少，所以不同的长度至多 $O(\sqrt {2n})$ 种。

于是可以优化到 $O(n \sqrt n \log n)$，然而常数极小。

原题：[ABC240Ex] Sequence of Substrings - 洛谷

代码：Submission #45730592 - AtCoder Beginner Contest 240

counting 庫的F序计数

有一颗「树」T，初始只有根节点 $1$。
「树」是一种很神奇的动物。
「树」能让女孩「祈求」，女孩会不断随机长度为 $n$ 的排列，直到排列是「可爱」的为止，每次随机称为一轮。
「可爱」的排列 $a$ 满足以下性质：如果 $i \ne 1$ 则有 $a_{fa_i} \lt a_i$。
「树」还能开啥用都没有的大招「妈妈生的」，从节点 $x$ 处下方额外再长出 $k$ 个孩子，「树」
不喜欢孤独的生活，因此保证 $k$ 是偶数，这些孩子会被分配新的编号，分别为编号最大值 $+1$ 到 $+k$。
现在，树会进行 $n$ 次操作，每次操作会先开个大招，然后让可爱女孩子「小 M」不断祈求，直到她祈求的排列可爱为止，输出小「小 M」期望祈求了多少轮。

可以推出答案为 $\prod siz_x$，于是问题转换为维护一个序列，支持区间加，全局求乘积。

然而考虑到 $k \equiv 0 \pmod 2$，模数为 $2^{16}$，也就是至多 $k^{16}$ 就没了。

于是维护区间乘积和懒标记是容易的了。

然而树剖加分块即可，平衡复杂度即可到 $O(n \sqrt {n\log v} \log v)$，得益于 uint16_t 的优良常数，完全可以过。

然而题解的复杂度是 $O(n \log^2 V \log n)$，思路类似，但是链上卷积和线段树：

讲每一个节点做成一个 $x + siz$ 的多项式，答案是 $x^0$ 的系数，直接做即可。

$\downarrow 2023.09.21$

CJ 的 P 题

rat 老鼠进洞

将 $n$ 位，有 $k$ 个 $1$ 的二进制映射到 $k - 1$ 个 $1$ 上，保证 $2k \gt n$。

人类智慧的，翻转最高的那一个位即可。

value 最大价值

定义 $F(l, r) = \frac {\sum_{i = l}^r a_i}{r - l + 1}$，多次询问，求 $\max_{i = l}^r \max_{j = i}^r F(i, j)$。

保证 $a_i$ 在 $[-1000, 1001]$ 内随机生成。

其实随机化保证了每一个点的单调栈长度期望为 $O(\sqrt n)$，根据醉汉走路（随机游走）的结论，尽管我不知道怎么证明。

发现修改特别多，于是可以有 $O(n \sqrt n + m \sqrt n)$ 的做法，也就是分块平衡复杂度。

然而人类智慧的，利用单调栈，答案一定不会太远，于是在单调栈上向前走 $2000$（也就是 $2V$）大概率就可以找到正确答案了。

其实 zjy 的代码中给出了另一种方法，但是不知道如何证明：

对于一个点，有用的只是其向前一边的一段：

也就是红色的那一段，而能作为答案的只有单调栈里面的东西，所以暴力跳即可。

for (int j = L[i]; j > R[i]; j = L[j]) ...
for (int j = R[i]; j > L[i]; j = R[j]) ...

$\downarrow 2023.09.23$（from $2021.11.04$）

博文阅读密码验证 - 博客园

ryx 构造

ryx 有一个非负整数 。他希望你构造出一个不超过 $40 \times 40$ 的矩阵，每个位置填 ryx 三者之一，使得连续的三个格子按顺序构成字符串 ryx 恰好有 $n \le 2222$ 个。

竖着，横着，斜着的 ryx / xyr 都算（一共 $8$ 种）

策略：

ryxyryx...
ryxyryx...
...

game 游戏

有 $n$ 间物理实验室，第 $i$ 间实验室有 $a_i$ 个人，他们全都在打游戏。

同学 A 可以选择进入一间实验室 ，然后让其中的所有 $a_i$ 个人停止打游戏。

然后老师 B 可以选择进入一间实验室 ，然后抓住其中所有在打游戏的人。

同学 A 的目标是让老师 B 抓到的人最少，而老师的目标是抓到最多的人。

老师 B 在决策时无法知道同学 A 进入过哪个实验室。

两人均选择最优决策，问老师期望可以抓到多少人。注意两人的决策都可以是基于概率的。

也就是说，你要找到一个 $m$，使得无论老师怎么操作，总存在同学的一种方案使得被抓的人数期望 $\le m$；同时无论同学怎么操作，总存在老师的一种方案使得被抓的人数期望 $\ge m$。

题意简述过来就是说，同学可以有一种方案 $\sum p_i = 1$，使得老师在每一个教室的期望收益为 $a_i (1 - p_i)$，显然老师会选择最大的那个收益，而同学需要最小化这个最大的收益。

所以考虑二分答案，判断是否可以构造出一组解，使得最大收益 $\le mid$。

由于需要保证 $\sum p_i = 1$，发现 $p_i$ 越小，$a_i(1 - p_i)$ 越大，所以考虑使得每一个教室收益都为 $mid$，判断 $\sum p_i$ 与 $1$ 的关系即可，如果 $\le 1$ 则显然有解，还可以再小一点 QwQ。

count 数数

对于一个排列 $P$，定义 $F(k)$ 表示所有长度为 $k$ 的子区间的最小值的最大值。

给出 $F(1), F(2), \cdots, F(n)$，求有多少个排列满足它，对于 $998244353$ 取模。

考虑给定一个 $P$ 如何快速的求出 $F$。

考虑从大往小加入每一个值 $x$，发现会形成一些段，不妨设最长段的长度为 $k$，于是发现对于 $F(1) \sim F(k)$ 都可以对于 $x$ 取 $\max$，又由于 $x$ 递减，所以可以利用并查集维护，做到 $O(n \log n)$ 求出。

于是发现限制转化为从大往小加入一个值 $x$，使得序列连续区间最大长度恰好为某个数。

正难则反，所以考虑从小往大加来限制。

最初只有一段长度为 $n$ 的区间，每次可以删掉 $1$ 的长度，使得一个区间分开。需要保证最长长度为某个数。

由于 $n$ 很小，并且可用的状态很少，所以利用 vector 状压即可。

dopetobly 滈葕（血型）

给 定 一 个 0/1 权 有 向 图 ， 给 每 个 点 赋 予 ABCD 中 的 一 个 字 母 使 得 每 条 有 向 边 都 满 足：$w = 1 \iff (t_x, t_y) \in \{(A, D), (A, B), (B, D), (B, A), (C, D), (C, A), (C, B)\}$

关系图可以长这样，于是我认识了滈葕是血型的谐音，于是如上图，发现关系看作 $a \to !a$，$b \to !b$。

于是相当于两套关系，而 $w = (a_x \wedge \neg a_y) \vee (b_x \wedge \neg b_y)$，考虑 2-SAT。

当 $w = 0$ 时，发现有四组关系：

• $a_x = 1 \to a_y = 1$，$a_y = 0 \to a_x = 0$，$b_x = 1 \to b_y = 1$，$b_y = 0 \to b_x = 0$。

当 $w = 1$ 时，利用布尔运算，将式子改写为：$(a_x \vee b_x) \wedge (a_x \vee \neg b_y) \wedge (\neg a_y \vee b_x) \wedge(\neg a_y \vee \neg b_y)$

于是又有了 $8$ 组关系。

拆点建边 2-SAT 即可。

$\downarrow 2023.09.26$

derby 德比

球队 P 和球队 Q 分别踢了 $n, m$ 场比赛。由于 P 和 Q 实力很强劲，所以不存在任何一场比赛 P 或 Q 的进球数为 （但是别的球队进球数可能为 $0$）。并且，有 P 或 Q 参加的比赛一定不是平局（即同场比赛参赛双方进球数一定不会相等）。你想知道，如果可以任意排列这些比赛信息，那么德比战的总进球数最多是多少？

排序双指针做即可。

tree 种树

他定义一棵子树的贡献为 $\frac {子树颜色数量}{子树大小}$,求最小贡献。

• 树上启发式合并

• 启发式合并

• 利用 dfn 序变成区间数颜色

walpurgis 瓦夜

现在有 $n$ 个魔法少女，每个魔法少女的攻击模式可以用一个三元组 $(x, y, z)$ 表示。其含义是，令 $a = highbit(x), b = highbit(y)$ ，那么对所有形如 $(x + sa, y + tb), s, t \in \N$ 的点产生 $w$ 的伤害，多次询问点 $(r, c)$ 收到的伤害数。

• 考场上的 $O(n \log V + n \log V (\log n + \log V))$ 做法（居然爆标了！），预处理出$(x, y)$ 的匹配前缀，放入字典树中，然后考虑暴力枚举 $r$ 的可以匹配的后缀，将 $c$ 放入对应的 trie 树中查询即可。
• 标程的 $O((n + m) \log V)$ 的做法，第一维可以放在 trie 上维护，第二维维护一个扫描线即可，两者是分开的 $O(\log V + \log V)$。

winter 赤冬

一棵树第 $i$ 个节点有 $a_i$ 个不同的学生。

现在我们需要给每条边定向。对于任意两个不同的学生，如果第一个能从自己所在的节点出发，沿着定向后的边抵达第二个学生所在的节点，那么称这两个学生是友好的。

求最多有多少对友好的学生。

结构一定是确定一个点 $x$ 作为根，并且对于 $x$ 的儿子 ，其子树要么全部叶向，要么全部根
向。

因为根的各个子树的外向点权和和内向点权和会乘起来贡献给答案，所以根选取树的带权重心可以更好的分配外向内向的子树大小。

确定了根之后，我们相当于就是对于一些点把它们划分成两个集合，满足两个集合乘积最大，由于度数 $\le 36$，直接折半搜索即可。

$\downarrow 2023.09.27$

博文阅读密码验证 - 博客园

cook 漂亮大厨

整道题相当于两个部分加起来：

TASK1：

两个操作：

• 区间加 $x \ge 0$。

• 区间求 $\le y$ 的数的个数。

显然线段树不好做，归并树也不是很好做，主要是 update 的复杂度不可保证。

所以考虑分块，首先有个很显然的 $O(\sqrt n \log n)$ 的单次复杂度，考虑优化其中散块排序的复杂度。

发现单独取出来归并即可做到散块 $O(n)$，所以可以做到 $O(\sqrt {n \log n})$。

题解说可以把询问离线下来，排序，使得块内变成单调查询。但是问题在于块内带修，不知道该如何做到省略这个二分的 $\log n$。

TASK2：

求 $n$ 个组合数前缀和 $f(n, m) = \sum_{i = 0}^m \binom{n}{i}$。

显然的可以莫队：

$$\begin{aligned} f(n, m + 1) &= f(n, m) + \binom n {m + 1} \\ f(n, m - 1) &= f(n, m) - \binom n m \\ f(n + 1, m) &= 2 f(n, m) - \binom n m \\ f(n - 1, m) &= \frac {f(n, m) + \binom {n - 1} m} 2 \end{aligned} $$

然而还有另外一种 $O(n \sqrt n)$ 预处理，$O(\sqrt n)$ 询问的方法。

如图，在最下面每隔 $O(\sqrt n)$ 取一个点，不断向上推即可，空间也是 $O(n \sqrt n)$ 的，非常优秀。如果离线下来空间可以 $O(\sqrt n)$。

eat 吃树

显然的结论是一棵树可以被分成大小为 $k$ 的 $\frac nk$ 个联通块当且仅当：

$$\sum_{i = 1}^n [siz_x \equiv 0 \pmod k] = \frac nk $$

于是类似埃氏筛一样开个桶记一下，复杂度可以接受 $O(n \log n)$。

fly 飞翔的胖鸟

给定 $a, b$ 求 $f(\theta) = \frac a {\sin \theta} + b \theta$ 在 $\theta \in (0, \frac \pi 2]$ 内的最小值。

显然凸函数，所以可以三分，但是 $T = 1e6$ 过不了。

考虑先求导，于是 $f'(\theta) = b - \frac {a \cos \theta}{1 - \cos^2 \theta}$。

于是关于 $\cos \theta$ 求一个方程即可求出最值的点。

注意 $b = 0$ 的情况。

bomb 漂亮轰炸

Spiders Evil Plan - 洛谷

给定一棵 $n$ 个节点的无根树，每条边有边权。

有 $q$ 次询问，每次询问给出 $x,y$，你需要选择 $y$ 条树上的路径，使这些路径形成一个包含 $x$ 的连通块，且连通块中包含的边权和最大。

$n, q \le 10^5$，强制在线。

如果没有必须经过 $x$ 的限制，显然的是可以转化为费用流模型然后长链剖分贪心求解。

然而必须经过 $x$，那么可以有两种优化方式：

• 去掉最小的链。

• 将一条链接下来。

所以倍增向上找到第一个被覆盖到的点，维护即可。

有一些性质：

• 对于一条到根的链，其长链的 $rank$ 是单调的。

• 对于一棵树，长链的个数即叶子节点的个数。

$\downarrow 2923.09.30$

game 小P的2048

小模拟……

interval 小P的单调数列

将一个数列划分为若干个极长的单调区间（相邻区间单调性相反），则这个数列的价值为所有元素的和除以区间个数。

要求找到给定序列的一个子序列，使得其价值最大。

不难有 $O(n^3)$ DP，由于要求相邻区间单调性相反。

令 $f_{i, j}$ 表示 $i$ 当前在第 $j$ 段的最大贡献。

$$f_i = \begin{cases} a_i + \max_{1 \le j \lt i, a_j \lt a_i} f_j \\ a_i + \max_{1 \le j \lt i, a_j \gt a_i} f_j \end{cases} $$

于是可以利用树状数组优化为 $O(n^2 \log n)$。

然而猜结论，区间个数一定不多，保守的可以做到 $O(n \log^2 n)$。然而有结论至多两个区间。

考虑为偶数，形如 $UDUDUD$，相当于是取一堆 $UD$ 的平均数，显然取最大的那个 $UD$ 更优秀。

如果为奇数，则相当于 $A, B, C$ 的平均数，显然取最大的更优秀。

故而至多取两个，所以只需要两次即可。

mst 小P的生成树

每个点有点权 $(a_i, b_i)$，定义一颗生成树的权值为 $\sqrt {(\sum_{x \in T} a_x)^2 + (\sum_{x \in T} b_x)^2}$。求最大生成树。

$n \le 50, m \le 200$

首先贪心骗分，然后 A* 骗分，再来模拟退火骗分……

考虑答案是什么，一堆向量加起来，到原点的距离。

如果知道答案了，考虑如何构造方案？类似于 kruskal 找最小生成树，发现似乎只需要按照到答案的向量的投影的长度排序即可。

于是考虑枚举这个投影的向量。

考虑类比 $2023.09.07 ~ T3$ 的做法，当斜率经过两点连线的垂线时才会影响他们的顺序，所以有用的斜率只有 $O(m^2)$ 个。

所以可以做到 $O(m^3 \log n)$ 了。

类似的考虑优化大概可以做到 $O(m^2 (\log n + \log m))$，然鹅不想写了。

然而有另外一个 $O(m^2 \log m)$ 的做法，将每一个合法的生成树看作一个点，则答案一定在凸包上。这不难理解。

于是需要使用最小乘积生成树中的 Quick Hull 算法求出凸包即可做到 $O(m^2 \log m)$。

这家伙跑的飞快，$O(m^3 \log m)$ 用了接近 $1s$，这里只用了不到 $15ms$！

walk 闲逛

给定一个 DAG，会随机选择一条当前位置能走的道路顺其走过去，如此反复直到没有能走的道路。

求每一个点为起点能得到路径权值异或和的期望。

拆位贡献拓扑即可。

$\downarrow 2023.10.01$

国庆还上课，受不了一点

park 公园

给定 DAG，$E \le 5000, V \le 2000$，定义有 $n \le 500$ 个起点，$m \le 500$ 个终点，起点和终点有其花费，每一个路径也有其花费。

只能从起点出发到一个终点，求花费在 $L$ 内最多能访问多少个点。

考虑 $O(EV)$ 拓扑即可，维护一个 vector 存 {len, cost}，每次归并，len 相同的选最小的 cost，这样每条边转移一次，每次转移是 $O(V + V)$ 的合并，所以总复杂度为 $O(EV)$。然而起点不多，卡不满上界。

plan 计划

如果一个区间 $[l, r]$ 内不同的颜色有 $\ge m$ 个，那么这个区间可以贡献 $r - l$，记为 $f(l, r)$。多次询问，求 $\sum_{i = l}^r \sum_{j = i + 1}^r f(i, j)$。

每个右端点至少从 $L_i$ 开始向前贡献，这可以双指针 $O(n)$ 维护。

离线扫描线，容易利用树状数组维护成 $O(q \log n + n \log n)$。

如果询问更多可以考虑 $O(n \sqrt n + q)$ 的做法。

然而可以做到更好，考虑类似的维护，一个前缀和。

贡献分成两部分，经过左端点的和完全在询问内的，预处理分开计算则可达到 $O(n + q)$ o_O?。

card 抽卡

有 $n \le 9$ 种卡，每种卡有 $3$ 个颜色，每次氪金抽 $m + 1 \le 64$ 次，前 $m$ 次每次每张卡抽出的概率为 $p_i$，不出卡的概率为 $1 - \sum p_i$，最后一次为 $q_i$。抽出一张卡颜色概率各为 $\frac 13$。

求所有卡所有颜色全部抽到，氪金次数的期望。

sol 1

令 $f_{i, s}$ 表示现在在氪金的第 $i$ 抽，手上每张卡的状态为 $s$。有转移方程：

$$f_{i, s} = [\sum p_k (\frac {c(s, k)} 3 f_{i + 1, s} + (1 - \frac {c(s, k)} 3) f_{i + 1, s_{(+k)}})] + (1 - \sum p_k) f_{i + 1, s} $$

于是可以按照 $s$ 从大到小，每一层高消一下，可以做到 $O(4^n m^3)$。

然而还不够，考虑优化，整理一下：

$$f_{i, s} = (\sum \frac {p_k \times c(s, k)}3 + 1 - \sum p_k) f_{i + 1, s} + \sum p_k (1 - \frac {c(s, k)} 3) f_{i + 1, s_{(+k)}} $$

发现后半部分是已知的，前半部分的系数也是已知的，所以问题相当于有一些系数：

$$f_{i, s} = a_i f_{i + 1, s} + b_i $$

并且我们知道 $f_{m, s} = f_{0, s} + 1$，所以我们可以倒推一下使得 $f_{0, s} = k_0 f_{m, s} + b_0$，从而解的 $f_{m, s}$，然后推回所有。

这是 $O(4^n nm)$，可以过。

sol 2

SMB 和 Meatherm 给出了 $4^n (n + \log m)$ 的做法，利用的是 min-max 反演。

考虑 $E(\max (S))$ 不具有线性性，所以需要转化为 $\min S$。

然而 min-max 容斥满足 $E(\max S) = E(\sum_{T \in S} (-1)^{|T| + 1}\min T)$

转化为加法之后就可以利用线性性 $= \sum_{T \in S} (-1)^{|T| + 1} E(\min T)$。

其中 $\max S$ 表示全部出现，$\min S$ 表示第一个出现。

于是 $\min S$ 可以通过其内元素的概率求出。

$\downarrow 2023.10.02$

差 T4 AK QwQ

stand 站军姿

傻逼贪心，咕……

look 向右看齐

有 $n$ 个 $0$ 和 $n$ 个 $1$，给定 $01$ 序列 $m$，对于一个长度为 $2n$ 的卡特兰 $01$ 串，求满足 $m$ 是其子序列的序列个数。 $n \le 200$。

考虑 $n^3$ DP 即可。设 $f_{i, j, k}$ 表示在第 $i$ 个位置，满足了 $m$ 的前 $j$ 个数，填了 $k$ 个 $1$ 的方案数。于是可是刷表了：

$$\begin{aligned} f_{i, j, k} &\to f_{i + 1, j + [M_{j + 1} = 1], k + 1} \\ f_{i, j, k} &\to f_{i + 1, j + [M_{j + 1} = 0], k} \end{aligned} $$

walk 齐步走

队列可以看作一个 $n \times m$ 的矩阵，若 $a_{i, j} = 0$，则会参照 $(i - 1, j)$，否则参照 $(i, j - 1)$。其有 $p_{i, j}$ 的概率和参照的人相反。假设 $(1, 1)$ 一定是正确的，求边界上的所有人相同的概率。

首先应该有一个顺着向下，$f_{x, 0/1}$ 表示不同/相同的概率，然而问题在于此时的答案可能存在内部一个点既是 $0$ 也是 $1$ 的情况。所以考虑倒着来。

设 $f_{x, 0/1}$ 表示 $x$ 的颜色为 $0/1$，子树内所有边点的颜色都为 $1$ 的概率 。

$$f_{x, 0} = f_{x, 0} \times (f_{y, 1} \times p_y + f_{y, 0} \times (1 - p_y)) \\ f_{x, 1} = f_{x, 1} \times (f_{y, 0} \times p_y + f_{y, 1} \times (1 - p_y)) $$

lighthouse 灯塔

将一个排列放在一个环上，给定 $m \le 20$ 个限制 $(x, y)$ 表示 $x, y$ 不能相邻，求方案数。

相对错排问题，$m$ 很小所以考虑状压容斥。

然而需要狠狠的判断当前状态不可构造的状态，并且特判只有一个 $n$ 环的状态。

现在剩下了 $l$ 条链，用了 $k$ 个点，于是方案数为 $(n - k + l - 1)! \times 2^{l - 1}$。

$\downarrow 2023.10.16$

tb trappola bewitching

给定 $n$ 个点的树，带边权，求 $\max \sum_{i = 1}^n x_i dis(i, x)$ 的最小值，对于 $10^9 + 7$ 取模，其中：

• $\sum x_i = 1, x_i \ge 0$

考虑如果知道了 $x_i$ 该如何求答案，发现需要最大化 $dis(i, x)$，所以自然 $x$ 就是直径的两端。

此时可以分析出答案的下界就是直径长度的一半，考虑 $\max(a, b) \ge \frac {a + b} 2$。

那么可以着手找到一种方法构造出下界，这是简单的，所以答案就是直径的一半。

cl conflict

对 $S = 2, 4, \cdots, 2 \times \lfloor \frac n2 \rfloor$ ，计算树上有多少个大小为 $S$ 的连通块满足如下条件：

• 存在一条边，删去该边后该连通块分裂成两个大小相等的连通块。

不难发现是树上背包 + 换根，树上背包的复杂度是 $O(n^2)$ 的，但是换根的复杂度就很难正确，需要卡上下界，然后求解，详见杂项。

ac Axium Crisis

有 $m$ 个元素，分布在树上，有两种操作：

• 元素编号为 $[l, r]$ 的向上跳一步（如果在根则不变）

• 求元素编号为 $[l, r]$ 的 $\mathrm{lca}$。

有两种方法：

• 轻重链剖分 + 线段树。这基于一个点跳重链到父亲之多需要跳 $\log n$ 次，否则每次 $dfn$ 只是 $-1$，所以这部分可以简单的 $O(m \log m \log n)$ 维护，其他的就很简单了。

• 发现操作一只会使得 $\mathrm{lca}$ 向上跳，于是可以利用 $dep$ 知道该如何跳，线段树维护是简单的，倍增跳一跳即可。

gl Grievous Lady

Luogu P8946，咕。

$\downarrow 2023.10.17$

$\mathrm{pity}$

xor 异或

对于一个元素介于 $[0, 2^m)$ 且互不相同的长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$，定义它的特征序
列为 $p_1, p_2, \cdots, p_{2^m - 1}$，其中 $p_i$ 表示使得 $a_{p_i}$ 与 $i$ 的异或值最大的下标。
形式化地，定义 $p_i = \arg \max_{1 \le j \le n} a_j \oplus i$ 其中 $\oplus$ 为异或操作。

求多少原序列满足此特征序列。

首先不难发现，原序列中的每一个数都应该在特征序列中出现，因为每一个 $a_i$ 都一定存在一个 $j$ 使得 $a_i \oplus j = 2^m - 1$，也就是最大。

根据二进制比大小的贪心策略，从高往低位思考序列的可能。

考虑这一位可以放 $0/1$ 需要满足左半和右半的特征序列必须相等，如果不相等，那么表明左右的高位不一样，我们递归下去求解即可。

但是在不相等时，我们必须保证没有重复元素，如果存在重复的元素，那么它的既要为 $0$ 也要为 $1$ 才能保证在两边都可以作为最大，显然冲突，此时无解。

graph 图论

$\mathrm{ICPC}$ 原题。

需要求出一个最大的阈值 $K$，每次连边 $(x, y)$ 必须满足 $deg_x + deg_y \ge K$，存在一个操作序列使得这张图变成完全图。

简单的 $O(n^3 \log n)$ 做法，二分答案，然后每次 $O(n)$ 代价连边即可。

很 naive 的 $O(n^3 \log n)$ 做法，利用优先队列维护最大的即可。

但是考虑 $Height$ 优化，考虑值域是 $O(n)$ 的，开点桶即可做到 $O(n^3)$。

然而存在更玄学的 $O(n^3 \log^2 n)$ 但是爆杀标程的做法（复杂度上界该不可能卡满）

还是先二分答案，每次 $O(n^2)$ 的尝试连边，但是先按照 $deg_x$ 排序，考虑每一连边一定是一段连续的区间，所以连完之后 $deg_x$ 还是单调的，所以可以大胆剪枝。

每次是 $O(n \log n)$ 的代价排序，至少连一条边，总共 $O(n^2)$ 条边，所以是 $O(n^3 \log^2n)$ 的，十分优秀（但是怎么可能顶满这个上界）。

video 视频

$\mathrm{Pity Simulation}$。

swap 交换

定义序列是好的，当可以分为先不减和后不增的两部分。

每次可以交换相邻两个数，求使得数列为好的最小操作次数。

考虑相当于从大到小加数，每次要么加左边，要么加右边。

代价就是已经加了的数在原序列中其左边或者右边的数的个数，这是容易使用树状数组维护的。

于是每次贪心的放在左边或者右边即可。

但是相同的数，把他们单独提出来，利用双端队列，两边贪心的选择 pop 并维护答案即可。

值得注意的是相同的数之间不相互贡献！

$\downarrow 2023.10.18$

coin 猜硬币

三堆硬币，找一个坏硬币，求最小操作次数。

有一个很简单的想法，每次选择一个最大的 $2^k$ 的部分使用 $(k - 1) + 1$ 次找，然后递归的处理剩下的部分。

然而可以用数学归纳法归纳出来查找的次数 $\lceil \log(a + b + c) \rceil \le x$，只需要判断是否可以等于下界即可（但是我不会判断）

holiday 假期旅游

优化 DP 式子：

$$\begin{aligned} f_1 &= H_1 \\ f_i &= H_i + \max_{1 \le j \lt i} (f_j - \lfloor \frac {j - i} K \rfloor \times D) \end{aligned} $$

注意到 $\lfloor \frac {j - i} K \rfloor = \frac {j - i} K - \frac {(j - i) \% K} K$。

于是可以转化式子：

$$\begin{aligned} f_i = H_i - i \frac dk + (i \% k) \frac dk + \max \left \{ f_j + j \frac dk - (j \% k) \frac dk + d \times [j \% k > i \% k] \right \} \end{aligned} $$

于是可以按照 $i \% k$ 分类，每一类维护一个支持动态加入，动态删除，动态求 $\max$ 的数据结构，然后统一用一棵线段树维护即可。

如果把等式两边同时乘上 $k$ 那么久可以直接 long long 维护了。

azusa 发电

Two Permutations (Easy Version) - 洛谷 Two Permutations (Hard Version) - 洛谷

给定两个排列 $p, q$，长度分别为 $n, m$。对一个长为 $t$ 的排列你可以按如下方式对 $i$ 进行操作：交换 $i$ 之间和 $i$ 之后的两端（相对顺序不变）。要求两个排列同时。你的目标是使得两个排列都有序。输出最小轮数和一种操作方案。无解输出一行一个 $-1$。

非常巧妙的构思，先考虑只是交换左右两部分（没有中间的不变点），形如 $AB \to BA$，如果是一个环，那么本质没有区别。所以我们考虑如何类比到这个操作上。

为了找到这个环，我们需要钦定其一个起点，不妨设为 $z$，那么对于 $zAxB \to zBxA$，如果稍稍对齐，那么就可以得到 $zAxB \to xAzB$，发现其本质就是交换 $x$ 和 $z$。

于是每次都可以将一个数和 $z$ 交换，求使整个序列有序的最小操作次数，而这是简单的。

但是这是一个环，所以最终状态可能有 $n$ 种：$n, z, 1, 2, ...$ 也是可以的。

所以每一种状态都需要枚举，然后求每次的操作次数。

然而有两个序列，如何做到最优？

不难发现的是，如果操作次数之差为偶数，那么只需要 $1, n, 1, n, ...$ 的补全即可。

然而在奇数的时候，我们至少需要 $n$ 次操作才可以使得长度为奇数的序列的操作次数奇偶性改变。

显然差为奇数的情况是不优的，所以我们分别记录两个序列最小的奇数次数和最小的偶数次数，分别判断即可。

此时可以简单的得到每次操作的数，模拟可以做到 $O(n^2)$ 还原整个操作序列。

题解区中可以做到 $O(n)$ 还原，但是其原理我不可得知。

alien 来自天外星系的地球旅人

$T$ 次询问，每次给定 $A, B, C \le 10^{18}$，求下式，取模

$$\sum_{1 \le x \le A} \sum_{1 \le y \le B} \sum_{1 \le z \le C} [y^x = x^z] $$

首先有如果 $y^x = x^z$ 那么 $x, y$ 一定可以表示为 $x = p^a, y = p^b$。

此时存在 $(p^a)^{p^b} = p^{bz}$，可以得到 $ap^b = bz$，注意特判一下 $p = 1$ 的情况，此时答案就是 $C$，于是后文默认 $p \gt 1$。

（这里符号有变化）于是式子化为：

$$C + \sum_{p > 1} \sum_{x = 1}^{\log_d A} \sum_{y = 1}^{\log_dB} [x \bot y] \sum_{z = 1}^C [yp^x = xz] $$

之所以需要 $[x \bot y]$ 是因为会在 $(\frac x {\gcd(x, y)}, \frac y {\gcd(x, y)})$ 的时候算到，所以需要互质保证不重复计数。

发现如果 $x, y, p$ 确定，那么 $z$ 也将确定，稍稍将 $p^x \le A$， $p^y \le B$ 和 $z \le C$ 的限制加上，可以得到：

$$C + \sum_x \sum_y [x \bot y] \sum_p [x | p^x] [p^x \le A][d^y \le B][z = y \frac {p^x}x \le C] $$

再化简一下

$$C + \sum_x \sum_y [x \bot y] \sum_p [x | p^x] [p^x \le \min(A, \frac {Cx}{y})][p^y \le B] $$

其实到这里就可以求出答案了。

考虑 $x = 1$ 时，后面的式子可以转化为 $\sum_p [p \le \min(A, \frac {C}{y})][p^y \le B]$。枚举 $y$，这在每一次都可以二分快速求解，注意 $p \gt 1$。

考虑 $x = 2$ 时，同理，转化为 $\sum_{y \equiv 1 \bmod 2} \sum_{p \equiv 0 \bmod 2} [p^2 \le \min(A, \frac {2C}y)][p^y \le B]$。同样 $p$ 的上界可以很容易的二分求出，此时只有一半的有用，故假定上界为 $k$，那么对答案的贡献为 $\lfloor \frac k2 \rfloor$。

剩下的时候考虑到 $A \le 10^{18}$，所以 $p$ 至多可以到达 $10^6$，于是预处理，对于每一个 $x$，枚举 $p$，判断是否满足 $[x | p^x]$，如果满足，加入一个数组中（注意是有序的），在求解的时候在这个数组中二分满足 $[p^x \le \min(A, \frac {Cx}{y})][p^y \le B]$ 的个数即可，注意 $\frac {Cx}{y}$ 可以爆 long long，这边建议使用 double 对 $10^{18}$ 取 $\min$。

接下来，如果发现 TLE，那么可以尝试如下卡常操作：

• 记忆化 $\gcd(x, y) = 1$，由于当 $x, y$ 很大的时候实际上的操作没有多少，而 $\gcd$ 可以高达 $10$ 次操作，所以很不优秀（能 $O(1)$ 就别 $O(\log)$
• 在预处理的时候，可以另开一个数组保存 $p^x$，这样在 $p \ge 3$ 二分的时候就不用计算 $p^x$ 了。
• 在 $p \ge 3$ 二分的时候，观察到如果 $x \ge y$ 并且 $p^x \le B$，那么一定有 $p^y \le B$，所以可以大胆的剪枝优化常数。

于是可以愉快的 $\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}$ 本题了。

代码链接：洛谷云剪切板

$\downarrow 2023.10.19$

maware 旋转吧

定义一个子矩形的相似度为包含在该矩形中的 $1$ 的个数与不在矩形中 $1$ 的个数的比值，求一个随机的矩形相似度为整数的子矩形的个数。

注意到时随机，所以期望合法的相似度不多，大概在 $20$ 左右，所以完全支持 $20n^3$ 写法。

于是横向 $O(n^2)$ 枚举，纵向 $O(n)$ 修改前缀和，然后 $O(20n)$ 查答案即可，期望得分 $100$。

irori 雪

定义一个 $01$ 序列是优美的，当且仅当不存在一个子区间，其中 $01$ 的个数的差的绝对值大于 $k$。计数由 $x$ 个 $0$ 和 $y$ 个 $1$ 构成的优美的 $01$ 序列的个数，取模。$n = x + y \le 10^5, k \le 10^5$

首先如果把 $01$ 看作折线，$0$ 向右下，$1$ 向右上，那么一个合法的路径纵坐标极差 $\le k$。

于是设 $f(l, r)$ 表示路径极大至多为 $r$，极小至少为 $l$ 的路径数，这可以简单的 $O(nk)$ 求出。

对于答案的计数的简单的，由于 $f(l, r)$ 有至少的加持，所以会重复计算，为了强制是的最小为 $l$，要减去 $f(l + 1, r)$ 的答案。

于是最终的答案为 $\sum_{i = 0}^k f(-i, -i + k) - f(-i + 1, -i + k)$，注意起点和终点。

然而不够优秀，不能通过此题，考虑翻折容斥，也就是卡特兰数折线法的扩展，每次按照斜线翻折，容斥既是。

yaya 月

对于一个常数 $w$，和任意一个正整数 $x$，你一次操作可以花费 $c(x)$ 的
代价将其变为 $\lfloor \frac x 2 \rfloor, \lfloor \frac x 3 \rfloor, \cdots, \lfloor \frac x w \rfloor$ 中的任意一个。$x, w \le 5 \times 10^4, q \le 10^6$

• 给定正整数 $x$，令 $c(x)$ 减少 $1$，保证任意 $c(x) \ge 0$。
• 给定正整数 $x$，求对其进行任意次操作后变为 $0$ 的最小代价。

呃，每次修改类似于 SPFA 松弛操作一次即可……然后就可以过这道题，不过注意建边需要 $O(\sqrt x)$ 的。根据出题人的分析，这复杂度在 $O(x w \log_w x)$ 左右，加上常数很很很小，所以可以过。

出题人说：考虑每次不暴力更新，而是枚举除掉的数是 $x$，那么能转移到的是一个
区间，可以使用线段树维护区间最大值和最大值点来维护，考虑这样做的复
杂度是 $O(x \log^4 x / \log w)$ 的，但是十分跑不满，所以是什么神秘的题 QwQ。

$\downarrow 2023.10.24$

square 方阵

有两个 $n \times n$ 的方阵 $A, B$，其中每一行每一列都恰好包含了$1 \sim n$，$n \le 200$。
现在你可以交换 $A$ 的任意两行或两列，问经过若干次操作之后，能否将 $A$ 变成 $B$？如
果可以输出最少的操作次数，否则输出 $-1$。

因为都是排列，所以考虑 $O(n)$ 的枚举 $A$ 的第一行会变化到 $B$ 的哪一行，这样列的变化就得出了。

接下来就利用哈希一一匹配即可，由于保证了每一列都是排列，所以不存在多对多的情况。

然鹅我在考场上没细看列是排列，写了一个随机化，被卡常乐……

cover 覆盖

有一个 $n$ 个点的树，你想要覆盖树上的所有边恰好一次。

1. 将 $u$ 到 $v$ 路径上的每一条边都覆盖一次。
2. 将与 $u$ 直接相邻的每一条边都覆盖一次。
   问最少的操作次数可以完成目标，注意每条边不能重复覆盖。

简单的树形 DP，但是我写挂了，没有验出来。

设 $f_{i, 0/1}$ 表示有一条链可以连出来，$can_i$ 表示连出来的那条是否存在某一条可以和其合并，转移如下：

$$\begin{aligned} f_{x, 0} &= - \lfloor \frac {cnt0 - 1} 2 \rfloor + [cnt0 = 0] + \sum \min(f_{y, 0}, f_{y, 1}) \\ f_{x, 1} &= 1 + \sum f_{y, 0} \end{aligned} $$

其中 $cnt0$ 表示 $\sum [f_{y, 0} \le f_{y, 1}]$，$can_x = [cnt0 \equiv 0 \pmod 2]$。

neginf 负无穷大

$n$ 次操作，每次将一个数设为 $-\inf$，每次求出 $|\sum_{t = i}^j a_t - k|$ 的最小值。

如果没有删除，存在一个 $n \log^2 n$ 的分治做法。

而如果多次删除，那么不可能每次都分治一次，这只适用于操作序列是随机的情况偏分。

于是发现每次操作使得一些区间没用，考虑逆着加数，使得一些区间有用，维护有用区间的信息。

于是利用并查集，以及启发式合并即可，应该是 $O(n \log^2n)$ 的。

spanning 生成树

有一个带权的无向图，我们定义生成树的权值为边权之和的 $k$ 次方。
问所有生成树的权值之和，对质数取模。

生成函数 + 矩阵树定理。

首先观察到 $(\sum w_i)^k = \sum_{\sum a_i = k} \frac {k!}{\prod a_i !} \prod w_i^{a_i}$，整理一下得到：$= k! \sum_{\sum a_i = k} \prod \frac {w_i^{a_i}}{a_i !}$。后面这部分很像 EGF，所以对于每一个边建立其边权的 EGF，得到最终的答案为 $k! [x^k] \sum_{T} \prod_{e \in T} F^{(e)}(e)$。

后面这个部分很像矩阵树定理，于是套用高斯消元的板子，只是其元素变成了 $F^{(e)}$ 而已。

如果存在一个多项式没有逆，这是不可以的，根据矩阵树定理，如果一个图联通，那么其行列式不为 $0$，也就是这个矩阵存在逆。而对于没有逆的多项式，其满足 $[x^0]F(x) = 0$，但是对于常系数来说，其与正常的矩阵树是一样的，所以一定存在一个 $[x^0]F(x) \ne 0$ 的多项式，其一定有逆。

于是可以 $O(n^3 k^2)$ 的完成，其中 $O(k^2)$ 是给多项式乘法和求逆的。

$\downarrow 2023.10.26$

tp 传送

JOISC2014

ball 排球训练

共有 $n$ 个同学一颗排球，这颗排球的初始能量为 $0$，一位同学只能接到能量小于等于 $b_i$ 的排球，由于都不会卸力，排球的能量会增加 $a_i$。
每位同学都想打排球，所以每位同学最多只能打一次排球。
可以随意安排同学的击球顺序，请问最多有多少位同学可以打排球。

首先考虑两个人的时候，发现让 $a_i + b_i$ 小的那个排在前面更优，于是合理外推，存在一个顺序，使得 $a_i + b_i \le a_j + b_j$，于是有 $O(n^2)$ 了。

此时考虑优化选人的过程，一定是能放则放，如果不能放，那么尝试取代放入中 $a_i$ 最大的那个。

这一定可以替代，因为存在 $a_i + b_i \le a_j + b_j$，且 $a_i \ge a_j$，所以存在 $b_i \le b_j$，那么代替是一定可行的。这利用优先队列维护即可。

这告诉我们有些时候需要大胆猜结论，或者多试几个常见的排序方法。

zvezda 繁星

求 $0 \le B \lt A$ 满足 $(A ~\^~~ B) \& C = 0$ 以及 $(A ~\^~~ B) \& C \equiv 0 \pmod 3$ 的 $B$ 的个数。

简单数位 DP 即可。

hamo 蛤膜

有 $q$ 次询问，每次给定一个左上角为 $(a, b)$，右下角为 $(c, d)$ 的子矩形，询问该子矩形绝对众数，如果不存在则输出 $−1$。

存在一个很厉害的做法，从二进制考虑。

如果一个数是绝对众数，那么每一个二进制位最多的那个都应该和众数一样。

于是在这道题里面，可以得到唯一的一个可能的数。

于是可以利用二维数点验证这个可能了。

$\downarrow 2023.10.18$

fft

有 $n$ 堆果子，每次合并两堆，得分是两堆个数的乘积，求所有可能的合并方法的总分数。

首先，不难发现总分和步骤没有必然的关系，总是 $\sum_{i = 1}^n \sum_{j = i + 1}^n a_i a_j$，这可以很简单的算出来。

然而考虑方案数，每一步都是在上一步的基础上任选两个，所以是 $n \choose 2$ 的。

所以总方案数为 $\prod_{i = 2}^n {i \choose 2}$。

lca

给定一个 $n$ 个点 $m$ 条边的简单无向图，求在图中最多可选出的不同的长度为 $2$ 的简单路径数量，使得每条边至多属于 $1$ 条路径。并给出构造。

类似于 IOI2019 景点划分 先找到一棵 dfs 树，从小到上贪心的删边即可。

odt

定义一个序列为锯齿序列当这个序列满足 $n \le 2$ 或者：

$$\forall i \in [2, n) (a_{i - 1} - a_i)(a_i - a_{i + 1}) \lt 0 $$

现在有 $n$ 个序列，初始为空，每次向 $[l, r]$ 的序列末尾加入 $x$，询问某序列最长的锯齿子序列，保证 $x$ 互不相同。

首先转化为查分序列，那么条件转化为 $b_{i - 1} b_i \lt 0$，于是考虑每一个的符号，得到答案即是连续的正负段个数 $+1$。

于是利用 $[lv, ls, rv, rs, cnt, len]$ 这个矩阵合并即可。

pair

给定 $n$ 对 $m$ 维空间中的点对，求平行于坐标轴且能够覆盖每个点对中至少一个点的 $m$ 维正方体的边长的最小值，点在正方体的边界上视为覆盖。

每对二选一，于是想到 2-SAT。

然而需要求下界，所以还要套一个二分 $x$。

假如当前选了某个点，那么每一维距离它 $\gt x$ 的都不可以选，考虑排序之后，这一定是一段前缀和一段后缀，于是可以前后缀优化建图。

然而还有二选一的限制，$\neg a \to b$ 即可。

于是总复杂度为 $O(nk \log n)$，时限十分紧张。

$\downarrow 2023.11.1$

merge 合并

在一次操作中，可以选择两个相邻的元素，将他们合并为两个数的和，求把一个数列变成回文的最小操作次数，$a_i \ge 0, n \le 10^6$。

如果存在一对 $i < j \text{ and } pre_i = suf_j$，那么合并次数可以减 $2$，两者都是单调的，贪心的匹配即可。

mahjong 麻将

期望 DP，题面过长，略。

发现每一种牌可以等价起来，考虑求的是期望出现时间，不难想到 $E(\max S)$ 利用 $\min - \max$ 容斥，于是成功没有做出来。

然而考虑合法的情况为 $13$ 张牌 $+1$ 张重复即可，记忆化搜索一下期望即可。

具体的，设当前状态 $f_{x, i, 0/1}$ 表示还有 $x$ 张牌可以摸，已经摸了 $i$ 种有用的牌，有无重复的，转移即可。

build 建造

每次可以选择一个区间 $[l, r]$ 和正整数 $x$，将 $[l, r]$ 格的楼房高度增加 $x$，求操作到目标序列的最小操作次数，$n \le 18$。

区间加自然的转化为差分数组上做。

于是发现一个长度为 $n$ 的差分数组可以只用 $n - 1$ 次完成，当且仅当其和为 $0$ 且其所有前缀和非负，这样就可以一对一对的消掉。

于是考虑 $O(3^n)$ 子集 DP 即可，但是注意卡常。

具体的，在枚举子集时，如果 $T \lt (S >> 1)$ 后，意味着其补集已经被枚举过，可以直接忽略，于是常数减半。

contest 比赛

超级数据结构题，题面过长，略。

考虑转移需要满足三个条件：

$$t_j + L \le t_i \lt t_j + R \\ c_j \le b_i \\ |a_j - a_i| \le h $$

第一个限制可以双指针，后面两个限制可以树套树，树状数组套平衡树即可做到 $O(n \log n)$ 空间，$O(n \log^2 n)$ 时间。

$\downarrow 2023.11.01$

copy 复制

每次将字符串的某一段复制，然后插入某个位置，求最终前 $k \le 200$ 的字符。

注意到 $k$ 很小，枚举每一个位置逆着推回原本的位置即可。

hard 硬币

对于一个 $01$ 序列，需要通过如下三种操作变化为目标序列，求最小操作次数：

1. 区间赋值为 $0$
2. 区间赋值为 $1$
3. 区间反转 $01$

首先，不难发现的是 $1, 2$ 操作不可相交，如果包含，可以利用 $3$ 操作代替。

于是每一个点被操作的状态只有 $6$ 个，为 $0/1/2/3/13/23$，于是可以 $O(3 \times 6)$ 的枚举上一个点的状态转移，为 $O(18n)$。

talk 演讲

# [JOI 2022 Final] 让我们赢得选举

假设我们选了集合 $A, B$，于是答案为 $\sum \frac {B_i}{i} + \sum \frac {A_i}{|B| + 1}$，发现按照从小到大选 $B_i$ 最优秀，可以得出贪心，按照 $B_i$ 排序，然后选人。

但是考虑到必须要 $|B| + 1$ 才能求后面的部分，于是需要枚举 $|B|$，然后进行一次 DP。

于是可以得出一个很简单的 $O(n^4)$，具体的，令 $f_{x, i, j}$ 表示前 $x$ 个人选了 $i$ 个 $b_i$，额外选了 $j$ 个 $a_i$ 的最短时间，可以 $O(n^3)$ 的做。

然而考虑优化：在最后选的 $b_i$ 前不可能存在既没有选 $a_i$，也没有选 $b_i$ 的存在，考虑前面的一定满足 $b_j \le b_i$，将 $i$ 替换为 $j$ 一定不劣，所以可以优化掉一位 DP，令 $f_{x, i}$ 表示选了 $i$ 个 $b_i$ 即可 。

tree 树套树

有两棵树 $T_1, T_2$，定义 $f(x, y) = dep[LCA_2(x, y)]$，求 $\sum_{u \le v} \sum_{i, j \in Path(u, v)} [i \lt j] f(a_i, a_j) \pmod {998244353}$。

首先不难有一个 $O(n^2)$ 做法，然后利用 CSP-2019树的重心 第二种方法优化即可做到 $O(n \log^2 m)$。

$\downarrow 2023.11.02$

game 博弈

在黑板上有 $n$ 个数字。Alice 和 Bob 轮流操作，每次从黑板上擦掉一个数字，所有数字都被擦掉时游戏结束。Alice 先手。

给定 $L, R$ ，Alice 获胜当且仅当她擦掉的数字之和不属于区间 $[L, R]$ 。判断谁
会获胜。保证 n 是偶数。

Alice 可以贪心的选择，要么最大，要么最小，判断是否不都在 $[L, R]$ 内即可。

count 计数

• 给定 n 个三元组 $(a_i, b_i, c_i)$ ，其中 $a_i, b_i, c_i \in [1, n]$。
• 在第 $i$ 轮，Alice 从第 $i$ 个三元组里删去一个数，然后 Bob 从剩下两个数里选
  一个拿走。
• 如果 Bob 拿到的 $n$ 个数两两不同，Bob 获胜，否则 Alice 获胜。
  给定 $a_i, b_i$ ，求有多少个 $c_i$ 使得 Alice 必胜，模 $998244353$ 。

首先整理出 Alice 胜的充要条件：存在一个数每一列至多存在一个。

反过来，那么就是 Bob 胜的充要条件为：每一个数存在在某一列存在两个。

由于只有 $n$ 列 $n$ 种数，那么 Bob 胜的充要条件为每一个数对应某一列且出现了两次。发现这是个二分图。

于是问题转化为给定一个二分图，求完美匹配数。

注意到左部点（下标）度数 $\le 2$，于是这个二分图对于每一个联通块中，至多存在一个环，并且如果有环的话，贡献将是 $2$，否则是 $1$。

注意存在不存在完美匹配的情况，此时设为 $0$ 即可。

于是利用总方案减去 Bob 赢的方案即可。

seq 序列

给定一个长度为 $n$ 的正整数序列 $a$ 。

对于一个区间 $[l, r]$ ，定义其权值为最大的 $x$ ，使得 $x$ 在 $a_{[l : r]}$ 出现且没有在 $a_{[1 : l − 1]}$ 和 $a_{[r + 1 : n]}$ 出现。特别地，如果不存在这样的 $x$ ，定义其权值为 $0$。

$q$ 次询问，每次给定区间 $[L, R]$ ，求 $[L, R]$ 的所有子区间的权值之和。

• SOL1：离线扫描线和历史版本和

扫描线，发现 $x$ 可以贡献的一定形如 $l \in [1, fst_x], r \in [lst_x, n]$，其中 $fst_x, lst_x$ 表示第一次/最后一次出现的位置。

那么每次扫描线相当于对于某个前缀取 $\max$ 然后求历史版本和。

利用 ODT 可以将区间取 $\max$ 变为区间加法，利用 矩阵标记 维护即可。

• SOL2：分治

非常 naive，可以做到 $O(n \log^2 n)$，只需要一个区间取 $\max$ 和区间求和的线段树即可。

$\downarrow 2023.11.04$

palin 另一个回文问题

给定一个 $n \times m$ 的表格，$(i, j)$ 位置填着字母 $c_{i,j}$ ，你需要从 $(1, 1)$ 走到 $(n, m)$，只能向下或向右走，且途径的字母需要构成一个回文串。查询方案数对 $998244353$ 取模的结果。

简单记忆化即可，注意只需要记忆化三维即可。

rap 说唱出门教学

你有一段长为 $n$ 的歌词，第 $i$ 个字的韵母被表示成一个小写字母 $s_i$。你要把这段话断成 $k$ 段，并最大化连押数（即每段歌词对应韵母的最长公共后缀）。

对于 $2 \sim n$ 的每一个 $k$，求出这个答案。

注意到固定一个 $k$，那么我们可以如此做：从末尾开始向前跳不相交的与 $k$ 后缀相同的地方，计数。

发现至多跳的级别在 $O(\sum \frac n i) = O(n \log n)$，所以考虑暴力跳，但是不可保证复杂度。

考虑利用线段树优化跳的过程，可以做到 $O(n \log^2 n)$，但是十分不优秀，于是考虑利用并查集优化，可以做到 $O(n \log n)$。

tree 树

这是交互题。

对于一棵 $n$ 个点的树，编号为 $1 \sim n$，每次可以给定一个点集 $S$，你会被告知满足以
下条件的点 $x$ 的个数：

• 存在 $u, v \in S$，满足 $x$ 在 $u, v$ 的简单路径上（包括端点）。

你需要还原树结构，要求询问数不超过 $8000$，点集和不超过 $3 \times 10^5$。

发现大概询问在 $O(n \log n)$ 级别，所以考虑如何做。

首先有一个很简单的想法，分层，然后每层之间 $O(n^2)$ 求（但是这样二叉树就会很抽象）

所以考虑一层一层来，还原树的结构，发现此时我们可以之间求出 $x$ 的父亲是否在其上一层的某个点集中，于是可以快速的二分。

这样应该是卡不满上界的，所以可以过。

kaleidoscope 万花筒

原本有一张无向带权图 $G$。小艾将它放到了一个万花筒里观察，这导致 $G$ 看起来会是它旋转产生的 $n$ 个副本的并。具体来说，对于每条边 $(u, v, w)$，会在 $H$ 中生成全体 $((u + i) \bmod n + 1, (v + i) \bmod n + 1, w)$ 的边。最后的图 $H$ 就是在万花筒中看到的结果。 求 $H$ 的最小生成树权值和。

考虑朴素的 Kruskal 的过程，能连则连，而在这里，利用 $\gcd(\mathrm{abs}(u - v), n)$ 即可求出连了多少边，剩下了多少块。

bubble 冒泡排序趟数期望

若排列 $p$ 在 $k$ 趟冒泡排序之后变为有序，则排列的权值定义为最小的 $k$。
给一个长度为 $n$ 的随机排列，求权值的期望值，对 $1e9+7$ 取模。

考场上我死磕了一个 $\max(i - P_i)$ 的结论，就是没有做出来……其实可以通过打表找规律……

然而考虑逆序序列：$I_i = \sum_{j \lt i} [P_j \gt P_i]$，则最终的次数为 $\max I$。

考虑这个序列性质十分优良，其与原序列一一对应，所以可以对其直接计数。

考虑 $\max I \le k$ 的逆序序列数，即 $k! \times (k + 1)^{n - k}$，于是 $=k$ 的两者一减，得到 $k! \times ((k + 1)^{n - k} - k^{n - k})$。

于是答案就简单了……QwQ

points 数点

给一个排列 $(i, P_i)$ ，放在平面上 。对于坐标上下限都在 $1 \sim n$ 内的全体 $(\frac {n(n + 1)}{2})^2$ 种矩形，求每个矩形内点数的 $k$ 次方和。

如果是 $k = 1$ 是简单了，贡献是独立的。

如果是 $k = 2$，那么发现两个点同时对某个矩形的贡献为 $2$，考虑：$(x + y)^2 = \sum \binom{2}{i}x^i y^{2 - i}$。

于是拆开来用树状数组统计一下即可，注意不要计算重复贡献！

如果是 $k = 3$，那么发现三个点同时对某个矩形的贡献为 $6$，两个点则是 $4$。

然而如何记三个点的情况，发现固定左/右点，那么存在下面 $6$ 种情况：

于是分开来做一次，利用线段树维护贡献即可。

$\downarrow 2023.11.6$

第二套，自己做的，曾经做过的。

openhook 开挂

每次你可以将一个 $a_i$ 增加 $1$，但由于开挂是有代价的，对第 $i$ 张牌执行一次操作有 $b_i$ 的花费。我可以在开始重排列 $b_i$，求使得 $a_i$ 互不相同的最小代价。

发现需要将数填到那些空位是容易确定的，唯一的问题是如何对应。

发现若 $a_i \le a_j \to a'_i \le a'_j$ 是不优秀的，也就是对应的覆盖区间不存在相交的。

所以每次贪心的放最大的那个需要放是最优的，利用栈维护一下即可。

clods 叁仟柒佰万

给定一个序列，你需要把它划分成任意多段，满足任意一段的 $mex$ 值相同，求方案数。

其实如果打个表可以发现划分之后每一段的 $mex$ 都是序列的 $mex$，首先一定不会是 $\gt mex$，考虑如果是一个 $\lt mex$ 的数，那么由于全局 $mex$ 可以知道这个数一定在某个位置出现了，也就意味着必定有一个区间的 $mex$ 不可能为所求的那个数。

于是考虑 $mex$ 的单调性，可以双指针求出每一个 $i$ 对应的左边最后一个 $= mex$ 的 $j$，利用前缀和可以直接转移。

总复杂度是 $O(n)$ 的，这非常 naive，感觉比 T1 简单。

charity 超级加倍

我们认为一条从 $x \to y$ 的简单路径是好的，当且仅当路径上的点中编号最小的是 $x$，最大的是 $y$。

请求出好的简单路径条数。

论 kruskal 重构树的另一种打开方式……点权！详见我的博客……其实我也是第一次发现可以如此理解。

$\downarrow 2023.11.08$

cool 清凉的午后

定义 $f_i$ 表示 $i$ 后第一个比他大的数的位置，认为 $A_{n + 1} = \inf$，给定 $f_i$，求一个字典序最小的原序列。

方法有很多，略略讲讲。

• 从前向后，发现每一个数其实就是剩下的数中第 $a_i - i$ 小的，利用树状数组维护即可。
• 从后向前，还原出每一个数前面比他大的数的个数，则是 $g_i$ 大的，同理维护。
• 从大到小，从左向右，一次填入即可，为 $O(n)$（也就是按照 $A_i$ stable_sort，一一放入即可）
• 利用单调栈模拟即可。

hotpot 火锅

这是一道交互题。

有两个数列，其一有 $1 \sim n$ 内的奇数，另一则有偶数，可以询问 $a_x$ 和 $b_y$ 的大小，在 $2 \times 10^5$ 次内还原两个数列。

先考虑经典的排序方式有那种可以使用，发现快速排序比较合适。

每一个 $b_i$ 可以将 $a$ 的某一块分成两块，于是可以二分出到底是哪一块即可（实际上二分出来可能的是两块，我们需要都尝试分一下）

然而 SMB 给出了另一种方法，考虑朴素的 $O(n^2)$ 其实就是在确定每个数的范围。

于是可以考虑优化这个过程，不断的减少可能的范围，如果没有交，那么其实大小关系已经出来了，就不用浪费一次询问了。

其本质上与快排的方法类似，但是更加简单暴力，值得参考。

release 放生

给你一棵以 $1$ 为根的树，边带权，两种操作。

• 修改某条边的边权。
• 询问以 $y$ 为根的子树中的每个节点到节点 $x$ 的距离和。

考虑有两种情况：

我们将边权下放到点权，每一条边的贡献拆开来看。

对于第一种情况，子树内的边贡献为 $\sum w_x \times siz_x$，子树外的为 $\sum w_x \times siz_y$。

也就是可以分成两个部分，一是子树内的 $\sum w_x \times siz_x$，第二是链上的 $siz_y \sum w_x$

对于第二种情况，不在 $x \leftrightarrow y$ 链上的边贡献仍然为 $\sum w_x \times siz_x$，但是在链上的则为 $\sum w_x \times (siz_y - siz_x)$。

也可以拆成三个部分，一是子树内所有的 $\sum w_x \times siz_x$，二是链上的 $siz_y \sum w_x$，三是多加的 $2 \sum siz_x \times w_x$。

于是利用树状数组和 dfn 简单维护链上和子树内信息即可。

注意到链修我们只是单点修，所以可以转化为树上差分，子树加和单点差，可以做到 $O(n \log n)$。

gentle 温柔

还不太会 QwQ Infinite Parenthesis Sequence

$\downarrow 2023.11.09$

题面都有点长，所以用截图

burger 汉堡

有点抽象，但是看着很像微扰贪心，于是从此入手。

考虑有两个部分：

我们需要最小化空白部分的大小，也就是 $a q_1 + b(n - q_1) + x q_2 + b(n - q_2)$。

考虑在 $l < r$ 两个位置的比较，如果 $q_1 = l$ 更优秀，那么存在：

$$al + b(n - l) + xr + y(n - r) < ar + b(n - r) + xl + y(n - l) \iff a(l - r) + y(l - r) < b(l - r) + x(l - r) \\ \iff a + y < b + x \iff a - b < x - y $$

与实际位置并没有影响，那么按照这个 stable_sort 一下即可。

ice 雪糕

首先很容易有一个 $O(n k + nm)$ 的做法，然而正解应该是 $O(nk + mk)$ 的。

我刚开始有一个很 naive 的想法，考虑区间加一个由转移矩阵 $T$ 生成的序列，这是容易用矩阵和线段树在线做到 $O(k^3 m \log n)$ 的。

因为注意到矩阵有分配律，所以这是合理的。

但是通过离线下来，每次加入一个开始的转移，每次减去一个转移，那么容易做到 $O(m k^2 + n k^3)$。

但是发现矩阵太笨重了，我们其实并不需要所有矩阵内的东西。

所以我们只需要记录前 $k$ 个数是什么即可，需要减去某个转移的时候，直接在这 $k$ 个数内减一减即可。

每次只需要 $O(k)$ 的转移，然后累加到原序列即可，注意前 $k$ 个数需要特殊处理一下（预先加到原序列上）

barbecue 烧烤

给定序列 $A$，可以任选两个数 $x, y$，求 $\min_{x, y} \max_{i = 1}^n \min\{A_i, A_i \oplus x, A_i \oplus y, A_i \oplus x \oplus y\}$。

首先我们容易确定 $x, y$ 的最高位应该是什么。也就是说将 $A_i$ 的后面几位抽出来，如果可以用两个数异或出所有，那么可以确定 $x, y$。

此时整个序列会划分为四个集合：需要异或 $x$，需要异或 $y$，需要异或 $x \oplus y$，不需要异或。

注意到答案满足单调性，那么考虑二分这个答案，然后判断。

首先如果不许要异或的集合中有 $> mid$ 的东西，那么妥妥不行。

于是对于前面三个集合，我们容易处理出合法的使得对于每个集合独立的 $\le mid$ 的那些 $x, y, z$。

于是我们只需要判断是否存在某一组 $x, y, z$ 满足 $x \oplus y = z$ 即可。

注意到这很像 FWT，所以可以用 FWT 做，将可行设为 $1$，不可行设为 $0$，那么来一次 FWT 就行了。

seaweed 水草

CF1474F 1 2 3 4 ...

$\downarrow 2023.11.12$

rescue 葫芦娃救爷爷

首先，我们让一个前缀的人去救，设人数为 $k$，概率和为 $P$，那么救出来的概率为 $\frac {(n - k)} n P$，剩下的有 $\frac kn$ 的概率救不出来，有 $\frac {n - k} n$ 的概率进入子问题。

那么既然有子问题了，还是独立的，那么就记忆化搜一搜即可。

network 网络图

一棵树，$m$ 个点对，需要对其路径定向，使得对于原树上每一条边正着经过的次数和逆着经过的次数差绝对值 $< 1$，构造方案，可以证明一定有解。

考虑一样一半，那么很欧拉回路。

如果我们能将这 $m$ 条边形成的图连成一个有欧拉回路的图，那么自然可以构造出解。

考虑我们需要将某些度数为奇数的点连起来，如果我们能够保证他们对应的路径在原树上没有交，那么就可以构造出一个方案。

于是将这些点挂在原树上，从下到上贪心，遇到两个点直接相连，这样就可以保证不相交。最后跑一跑欧拉回路即可。

mexmax 么克斯马克思

定义 $f(k) = \mathrm{mex}_{r - l + 1 = k} \max_{i = l}^r a_i$，多次询问，求 $f(k)$。

首先，我们考虑 $x$ 什么时候可以存在，也就是可以被取到。

发现如果 $k \le$ 最长的全部 $\le x$ 并且包含 $x$ 的连续段，那么就可以被取到。

也就是说，对于每一个 $x$ 来说，都会对于某一个长度 $k$ 限制其取不到 $x$，也就是其答案 $\le x$，那么如果我们对于所有 $x$ 都对答案限制一下即可直接求出答案。

方法有很多，单调栈，并查集什么的都可以做，复杂度最优是 $O(n)$，并查集是 $O(n \alpha(n))$。

cycles 数圈圈

给你一张无向图，请你数数其中有多少个 $k \le 6$ 元环。

对于 $k \le 4$ 都是简单好做的。

对于 $k > 4$，可以通过矩阵加复杂度容斥和分讨搞定，但是太抽象。

不过发现分讨几乎都和 $2$ 元环相关，如果我们能够将二元环给去掉，自然是最好的。

于是考虑 $M_k$ 表示走 $k$ 次从 $i \to j$ 的方案数，如果要容斥掉二元环，那么只需要 $M_k = M_{k - 1} G - M_{k - 2}(D - I)$ 即可。

其中 $G$ 是邻接矩阵，$D$ 是度数矩阵，至于减去 $I$ 那个矩阵，是防止走向来时的那条边，走回来。

这个思路来自于 European Trip

$\downarrow 2023.11.14$

train 草莓列车

给定一个序列，有 $m \le 1e7$ 次操作，形如 $(l, r, v)$ ，表示将 $[l, r]$ 的每个 $a_i$ 变为 $\max(a_i, v)$，求最终的序列。

首先类似线段树可以做到 $O(n + m \log n)$，这在本体中显然不可取。

于是考虑另一个 RMQ 问题的利器，Sparse Table，顺着用可以做到 $O(n \log n + m)$，那么逆着用也就是本题了。

path 草莓路径

全局异或最大路径。

经典的 dfs + 环，于是问题转化为在一个数列中选两个数，异或起来放在线性基中最大。

由于异或线性基可以随意凑出所有主元，但是其他的就无能为力，我们将所有的 dis[x] 消去主元，看能剩下些什么东西，然后拿出另一个 dis[x]，加入所有主元，放入 trie 中查最大异或对即可。

相当于基于主元的贪心，线（贪）性（心）基。

city 草莓城市

草莓城是一个个四个角坐标分别为 $H \times W$ 的矩形，其中有 $k$ 个草莓，草莓所在的点都是整点。现在要给每个草莓建一个大棚，满足大棚都处在城市内，且互不相交（指被多个大棚覆盖的区域面积为零）。要求每个大棚的形状为等腰直角三角形，对应草莓处于斜边的中点，且斜边与一条坐标轴平行、所有三角形的斜边长度相等。

请你设计一个方案使得斜边的长度最大。

在 算法学习笔记(38): 2-SAT 中讲了。

easy 草莓之歌

[JOISC 2023 Day3] Chorus

$O(n^3)$ 是简单的，不提。

然后利用种种神秘优化即可，我不会。

$\downarrow 2023.11.14$

bing 并王

给定序列，求 $\sum_{i \lt j \lt k} (a_i \oplus a_j) | a_k$

简单拆位贡献即可。

fenwick 树状数组

第一次在考场上做出这种 $P$ 题，当时激动极了，甚至做完的后还有 1h30min。

有 SmallBasic 讲的优秀做法，为 $O(k^3)$，可以与 $m$ 没啥关系。

这里说说我的做法。

我们要求的是 $E[\sum c_x^k]$ 利用期望线性性，一点一点来：

$$\begin{aligned} E[\sum c_x^k] &= \sum E[c_x^k] \end{aligned} $$

考虑对于每一 $c_x$ 贡献的序列是不一样的，我们对于每一个 $c_x$ 拆为 $\sum a_i$，也就是每次操作对 $c_x$ 造成的影响序列（与随出来的序列 $v_i$ 区别开），那么：

$$E[c_x^k] = E[(\sum a_i)^k] $$

注意到 $a_i$ 之间相互独立，所以我们可以考虑一个一个加数的过程，令当前操作到第 $z$ 次，令 $C = \sum_{i = 1}^{z - 1} a_i$

那么利用二项式定理，我们有：

$$E[(C + a_z)^k] = \sum \binom{k}{i} E[a_z^i] E[C^{k - i}] \tag{1} $$

注意到初始 $E[C^k] = [k = 0]$，那么我们只需要求出 $E[a_x^i]$ 就可以如此卷积 $m$ 次知道最终的答案了。

此时我们只需要关注 $a_z$ 的取值，考虑每一个值的概率。

我们不难发现，对于每一个 $x$ 来说，能够影响到它的位置有 $\mathrm{lowbit}(x)$ 个，这是树状数组本身的性质决定了。

于是我们设 $P = \frac {\mathrm{lowbit}(x)}n$，那么 $E[a_z^k] = (1 - P) \times 0^k + \frac {P}{S + 1} \sum_{i = 0}^{S} i^k$，后面的 $\sum_{i = 0}^S i^k$ 容易 $O(k^2)$ 或者 $O(k)$ 的利用插值解决。

注意当 $k = 0$ 时，无论如何 $E[a_z^0] = 1$。

那么我们只需要 $(1)$ 不断的递推即可，可以做到 $O(k^2)$ 预处理 $\sum_{i = 0}^S i^k$ 以及 $O(k^2 m)$ 递推。

但是 $m$ 很大，我们考虑每次递推的转移是一定的，于是考虑利用类似快速幂的思路优化转移。

考虑如何证明结合律？

将两者看作两个多项式，$k! [x^k]F(x) = E[C^k], k! [x^k]G(x) = E[a_z^i]$，那么考虑多项式的卷积满足结合律，所以这里可以利用类似快速幂（$\mathrm{FaKe}$ 多项式快速幂）的优化。

此时我们对于每一个不同的 $\mathrm{lowbit}(x)$ 都可以做到 $O(k^2 \log m)$ 的复杂度，而本质不同的 $\mathrm{lowbit}(x)$ 有 $O(\log n)$ 种，于是总的复杂度为 $O(k^2 \log m \log n)$。

然而我们还有优化的空间，考虑利用多项式快速幂，我们可以做到 $O(k \log k \log n)$，连 $m$ 都没有了。

---

现在说说 SmallBasic 的想法。

首先我们将 $E[c_x^k]$ 朴素的式子写出来，其中 $P = \frac {\mathrm{lowbit}(x)}{n}$：

$$\sum_{i = 0}^m \binom{m}{i} P^i (1 - P)^{m - i} \sum_{\sum_{j = 1}^i t_j = k} \left(\frac{k!}{\prod t_j !} \prod (\frac 1 {S + 1} \sum_{v = 0}^S v^{t_j}) \right) $$

我们可以预处理出自然数幂和，$SP_k = \sum_{v = 0}^S v^k$，那么化为：

$$\sum_{i = 0}^m \binom{m}{i} P^i (1 - P)^{m - i} (\frac 1 {S + 1})^i \sum_{\sum_{j = 1}^i t_j = k} \left(\frac{k!}{\prod t_j !} \prod SP_{t_j} \right) $$

发现后面实际上是一个背包的形式，并且考虑到不为 $0$ 的 $t_j$ 只有 $O(k)$ 个。

那么我们可以先做一次背包，设 $g_{i, k}$ 表示有 $i$ 个 $> 0$ 的 $t_j$，次数和为 $k$ 的系数。

转移大概就是说：

$$g_{i, k} = \sum_{1 \le j \le k} g_{i - 1, k - j} \times \frac {SP_j}{j!} $$

那么我们可以将上式化为：

$$\sum_{i = 0}^m \binom{m}{i} P^i (1 - P)^{m - i} (\frac 1 {S + 1})^i \sum_{j = 0}^{\min(i, k)} \binom{i}{j} g_{j, k} SP_0^{i - j} $$

考虑将 $j$ 那一维提前一下：

$$\begin{aligned} &= \sum_{j = 0}^{\min(m, k)} g_{j, k} \sum_{i = j}^m \binom mi \binom ij P^i (1 - P)^{m - i} (\frac {1}{S + 1})^i SP_0^{i - j} \\ &= \sum_{j = 0}^{\min(m, k)} g_{j, k} \binom mj SP_0^{-j} \sum_{i = j}^m \binom{m - j}{i - j} P^i (1 - P)^{m - i} (\frac 1 {S + 1})^i SP_0^i \\ &= \sum_{j = 0}^{\min(m, k)} g_{j, k} \binom mj SP_0^{-j} \sum_{i = 0}^{m - j} \binom{m - j}{i} P^{i + j}(1 - P)^{m - i - j} (\frac 1 {S + 1})^{i + j} SP_0^{i + j} \\ &= \sum_{j = 0}^{\min(m, k)} g_{j, k} \binom mj (\frac 1 {S + 1})^j P^j \sum_{i = 0}^{m - j} \binom{m - j}i P^i (1 - P)^{m - j - i} (\frac 1 {S + 1})^i SP_0^i \\ &= \sum_{j = 0}^{\min(m, k)} g_{j, k} \binom mj (\frac 1 {S + 1})^j P^j (SP_0\frac {P}{S + 1} + 1 - P)^{m - j} \\ \end{aligned} $$

这一种方法复杂度上线在处理 $g_{i, k}$ 的地方，为 $O(k^3)$ 的，插值的部分是 $O(k^2)$ 的，但是每次计算却是仅仅 $O(k)$ 的（快速幂带个 $O(\log m)$ 也行）。

但是能过……于是我们可以愉快的 $\texttt{\colorbox{#52C41A}{\textcolor{white}{AC}}}$ 本题啦。

island 岛屿旅游

考场上我胡了一个 $O(n^5)$ 的东西，成功豪夺 $30$ 分，大概是设 $f_{i, k}$ 表示到 $i$ 做 $k$ 次飞机的最小代价，$k$ 是 $O(n)$ 级别的，所以暴力转移 $O(n^5)$ 是简单的。

我们考虑换一个状态，设 $f_{i, k}$ 表示代价为 $k$ 至多能做多少次飞机，注意直飞成本为 $O(n)$ 的，所以 $k$ 也为 $O(n)$。

这是一个背包的形式，我们考虑怎么建图转移。

观察如图形式：

发现其实蓝色的边是没有用的，因为不如用两条橙色的边优。

于是我们可以简单推出一个结论，我们只需要连的边所占据的矩形中不包含其他的陆地。

那么我们就可以 $O((nm)^2)$ 的建图了，这样边数是 $O(n^2)$ 的，于是转移是简单的 $O(n^3)$ 的，瓶颈在建图上。

如何建图，我们可以利用单调栈。我们每一列每一列的处理，如图所示，橙色是需要连的边：

发现我们只需要按照横坐标作为值，维护一个单调栈即可。但是需要注意最下面这种在同一行的情况也需要连边。

这复杂度每一列是 $O(n)$ 单调栈，$O(n^2)$ 连边，所以总复杂度为 $O(n^3)$，可以过。

需要注意 DP 数组的缓存问题，不然会很 TLE

maya 玛雅历

和儒略历很像。

他们都是 400 年的跳，这里给一个很 naive 的做法。

直接转化为天数，二分出某一年到 3113 BC 没有这么多天，然后在这年搞就是了。

---

省选篇

$\downarrow 2023.12.11$

interval 区间

给定 $n \le 1e5$ 个区间，求最多选出多少对区间，使得两个区间不交。

利用网络流很容易建模，但是需要对于一个矩形内的点连边，这是 $O(\sqrt n)$ 的，再加上网络流的复杂度，很不可接受。

但是既然可以网络流了就考虑网络流的经典套路：

• 模拟网络流/费用流
• 反悔贪心

这里利用反悔贪心即可。

apers

给定无向图 $G$，需要保证任何一条从 $s$ 到 $t$ 的路径都会经过至少 $k$ 个地雷。每个节点上只能放置最多一个地雷，且在 $x$ 号节点上安放一个地雷需要付出 $C_x$ 的代价，求最小代价。

考虑 $k = 1$ 就是最小割经典模型，将点拆为入点和出点，中间连 $C_x$，跑最小割即可。

然而需要有 $k > 1$ 个地雷，考虑分层，流与原图的路径一一对应。

每次割掉 $C_x$ 后经过这个路径的流一定向上层，也就成功的变为了子问题。

那么建出图来跑最小割即可。

circles

现在有一张 $2n$ 个点的二分图，左边 $n$ 个点，右边 $n$ 个点。其中左边第 $n$ 个点与右边个点有边。

你需要求出图中总共有多少个不同的简单环。简单环在这里指一个点只被经过至多一次的环。

菜，连签都不会……

考虑每一个点连的是一个前缀，那么形成的联通块也就是一些些链。

令 $f_{i, j}$ 表示前 $i$ 个点分成 $j$ 个联通块的方案数，按照 $i$ 是左部点还是右部点来讨论。

新增的点要么是新开一个块，要么是合并两个块，简单转移即可。

$\downarrow 2023.12.15$

CMD 被盒了 QwQ：NOI2021年排名21名杨宇辰同学

color 染色

进行 $n$ 次操作，第 $i$ 次操作可以选择某 $k$ 个连续方格染成颜色 $i$。

初始时方格颜色为 $0$，最终会形成若干个相邻颜色不同的位置，称为一种局面，求本质不同的局面个数。

发现如果存在若干连续的 $\le k$ 的颜色段，那么至少存在一个 $= k$ 的颜色段才是可能构造出来的。

由于 $\le k$ 的颜色段怎么都可以被一种颜色覆盖，那么使得所以 $\le k$ 的颜色段都有色算了。

于是考虑一个 DP，$f_{i, 0/1}$ 表示有 $i$ 个元素，最后一段是否存在 $=k$ 的段，其他都是合法的方案数，那么有转移：

$$\begin{aligned} f_{i, 0} &\to f_{i + j, 0} &(j \lt k) \\ f_{i, 1} &\to f_{i + j, 1} &(j \le k) \\ f_{i, 0} &\to f_{i + j, 1} &(j = k) \\ f_{i, 1} &\to f_{i + j, 0} &(j \gt k) \end{aligned} $$

发现能拿来用的只有 $f_{i, 1}$ 的东西，考虑如何利用这个凑出答案。

发现整个纸条两侧可能有空白，可能只有一侧，也可能没有，分别讨论，可以得到：

$$f_{n, 1} + 2 \sum_{i = 1}^{n - k - 1} f_{i, 1} + \sum_{i = 1}^{n - 2k - 2} (n - 2k - i - 1) f_{i, 1} $$

设 $S_n = \sum_{i = 1}^n f_{i, 1}$，那么可以将式子改写为：

$$S_n - S_{n - 1} + 2 S_{n - k - 1} + \sum_{i = 1}^{n - 2k - 2} S_i $$

补充一下 $\sum_{i = 1}^{n - 2k - 2} (n - 2k - i - 1) f_{i, 1}$ 是怎么转换到 $\sum_{i = 1}^{n - 2k - 2} S_i$ 的。
简单来说，就是将竖着求和变成了横着求和：

将转移写成填表法的形式：

$$\begin{aligned} g_{i + 1, 0} &= 2 g_{i, 0} - g_{i - k + 1, 0} + g_{i, k, 1} \\ g_{i + 1, 1} &= 2 g_{i, 0} - g_{i - k, 1} + g_{i - k + 1, 0} \end{aligned} $$

那么就可以利用矩阵快速幂 $O(k^3 \log n)$ 的求解这个问题了，其中 $S_n$ 多开一位快速幂时顺便累加即可。

transport 货车运输

给出 $n$ 个点 $m$ 条边的无向连通图,边的编号为 $1 \sim m$,边的权值是一个 $1 \sim m$ 的排列。
记 $d(u, v)$ 为 $u, v$ 之间最大边权最小的路径中的最大边的编号。给出所有的 $d(u, v)$，求有多少种给边赋值的方案符合限制（保证至少存在一种方案符合限制），答案对 $10^9 + 7$ 取模。

注意到 $d(u, v)$ 实际上是限定了整个图的 kruskal 重构树的形态。

那么我们可以还原出这颗树，但是会剩下一些边，可以简单的连在满足条件的最高点，那么就是一个树上拓扑序计数的问题。这可以归约为堆方案数，典。

$\downarrow 2023.12.18$

math 代数

这道题倒是十分巧妙。

不妨先考虑最终的局面，只有 $\le n$ 个位置有值，那么对于行列式的定义来说，其有值当且仅当矩阵满秩，在这里就要求每行每列均有值。

于是来一发经典思想：横纵坐标相互独立。细细琢磨之后发现其成立，那么我们将一个二维问题转化为一个一维问题。

现在就是考虑若干的区间，需要在每一个区间内选择一个点，求逆序对的奇偶性。

根据某大佬的想法，我们可以利用 双射 来干掉一些情况。

考虑两个相交的区间：

如果我们交换两个的位置，那么逆序对数的奇偶性一定改变，而交换前后一一对应，也就是说这种情况会被相互抵消。

考虑消掉这种情况，也就是将某个区间的范围缩小即可。

哦，发现每一个变成了 $n$ 个不相交的区间，并且考虑到只有 $n$ 个位置，所以说这样消出来的东西是一个排列，并且是唯一的！

那么我们只需要求一次逆序对看看奇偶性即可。但是需要注意如果有地方没有被覆盖那么 return 0 即可。

接着考虑到横竖互相独立，将答案两者的 $\det$ 求出来即可。

最后我们需要求期望，除以分别的总方数即可（因为我们分开考虑了的）

pigeon 鸽子

给定一张带边权二分图，$n \le 1000, m \le 100000$，对于 $k \in [1, n]$ 求出选出 $k$ 个匹配使得最大边权最小，并输出。

首先 $O(n^2 m)$ 或者 $O(n m \sqrt m)$ 利用匈牙利算法或者网络流是简单的，但是显然不太能过。

考虑到最大流 $f(n) \le n$，那么我们可以只在可以增广时才增广，至于如何判断，不可能真的用有向图连通性的算法，但是可以考虑在此基础上利用必要条件剪枝。

在残量网络上，考虑如果加一条边后可以增广的必要条件是连接了 $S, T$ 所在的两个联通块，利用 dinic bfs 得出的 dep 可以很好的判断连接的边是否是可能增广。

但是这当然是可以被卡的：

就可以每次增广一遍，但是却不会增加流，使得复杂度变成 $O(n m^2)$，绷。

至于作者所说的 $O(nm)$，我很是无法理解。

chess 棋子

[USACO21JAN] Minimum Cost Paths

所以说它本身是一个保序回归经典问题，但是我用另一种方法将它做了出来。

首先看到朴素的 DP：

$$\begin{aligned} f_{i, j} = \min(f_{i - 1, j} + C_j, f_{i, j - 1} + i^2) \end{aligned} $$

考虑到 $j$ 这一维很小，考虑是否能够对其做一个扫描线。

那么首先修正转移的顺序，对于列 $j$，我们先统一令 $f_{i, j} = f_{i, j - 1} + i^2$，也就是先从上一个版本转移过来。

再考虑列内转移 $f_{i, j} = \min(f_{i, j}, f_{i - 1, j} + C_j)$。

发现如果可以转移，当且仅当 $f_{i, j} > f_{i - 1, j} + C_j$，稍微移项，写成 $f_{i, j} - f_{i - 1, j} > C_j$ 的形式，发现这是差分的形式，考虑将转移变成差分然后维护。

令 $g_{i, j} = f_{i, j} - f_{i - 1, j}$，那么可知 $f_{i, j} = f_{i, 1} + \sum_{2 \le k \le i} g_{k, j}$，如果我们可以在扫描线时维护这个差分，那么求答案就变成了一个简单的前缀和问题。

考虑转移如何转移，我们对于列 $g_i$ 统一执行 $g_{i, j} \leftarrow g_{i, j - 1} + i^2 - (i - 1)^2 = g_{i, j - 1} + 2i - 1$，发现相当于全局加一个一次函数。

然后对于列内的转移，相当于对于全局取 $\min C_i$，由于我们需要求前缀和，所以这个问题是不可做的，但是我们可以通过性质绕开它。

考虑我们可以归纳证明 $g_i$ 是一个不降的函数，那么对于全局取 $\min C_i$ 就可以变为对于一个后缀赋值的问题。

在 $i = 1$ 时，有 $g_{1, j} = C_1$，在进行第一步转移时，我们加上的是一个单增函数（并且没有负数），那么转移后的 $g_{1, j}$ 仍然是一个不降函数，并且显然的全局取 $\min C_2$ 后仍然不增。

类似的，我们可以证明对于任意 $i$ 转移后仍然是一个不降的函数，那么我们就可以将全局取 $\min C_i$ 变为区间赋值问题。

那么我们就将问题转化为如下对于一个序列上的问题：

• 全局加一次函数
• 找到第一个 $> C_i$ 的位置，并对找到的后缀赋值
• 查询前缀和

这可以利用动态开点线段树用 $O(m \log n)$ 的时空代价完成，于是我们就搞定了这道题。

代码链接：云剪切板

---

然而利用保序回归更加无脑且简单，只需要单调栈即可。

由于本人太菜，不会……

$\downarrow 2023.12.22$
@bill666 出的题，有点阴间

algebra 线性代数

给定 $m$ 个 $n \times n$ 的 $01$ 矩形，求本质相同的矩形的数量，这里指可以通过任意次反转 $2 \times 2$ 的子矩阵转化为另一个矩阵。

非常简单，将 $(n - 1) \times (n - 1)$ 全部消为 $0$，那么剩下的东西是唯一的。

那么如果矩阵本质相同，剩下的东西也相同，随便利用 map 或者 trie 匹配一下即可，复杂度 $O(n^2 m + n m\log m)$。

write 写作与沟通

给定平面图，每个点度数至多为 $4$，保证存在欧拉回路，求解一条欧拉回路使得转过的角度最小。

首先容易想到一个神秘的贪心，对于度数为 $4$ 的点，取最小的那对即可。

但是可能不止形成了一条欧拉回路，下图就可卡掉这个贪法。

于是 SMB 给出了一种思考，考虑这种情况出现，中心点为割点，那么配对的边不能属于割掉后的同一个联通块，那么贪心时特判一下即可。

但是仍然有问题，考虑下图

类似状物就可以卡掉，因为中心点不一定是割点。

但是里正解不远了，仍然贪心，发现形成了多条通路，我们需要合并他们，那么在 $X$ 状物处可以合并，但是需要花费一定代价，最终需要使得所有通路联通，那么就是一个最小生成树的问题，随便跑跑就完事。

我考场上太 naive 了，简单想了想贪心，感觉对的就写了……应该尝试构造数据 hack 一下，之后的测试需要大大锻炼这个能力，不然太浪费了。

fireproof 组合数学

太阴间了，咕

$\downarrow 2024.01.08 day$

wheat 小麦

给定 $A$ 满足 $1 \le A_i \le n \le 500$，记 $C_i$ 表示 $B$ 中 $i$ 出现的次数，求满足 $1 \le B_i \le n$, $C_i \le A_i$, $C_{B_i} \le A_i$ 的 $B$ 的个数，对于 $998244353$ 取模。

第一个限制限定值域，第二个限制限定个数，第三个限制限定位置。注意到复杂度可能是 $O(n^3)$，考虑这个计数该如何 DP。

枚举每一个限制作为 DP 的第一维，发现对于个数的限定在倒序考虑的时候非常容易，因为限定范围不断变大，这是容易处理的。于是考虑设 $f_{i, j, k}$ 表示出现次数 $\ge i$ 的数有 $j$ 个，一共出现了 $k$ 次。

然而类似背包的考虑，记 $S_i = \sum [A_j \ge i]$：

$$f_{j, k} \leftarrow f_{j - 1, k - i} \binom {S_i - (j - 1)} 1 \binom {S_i - (k - i)} i $$

是错误的……因为会多一个关于 $i$ 个选择的数的个数的系数无法处理。

所以必须枚举一个选择的个数：

$$f_{i, j, k} = \sum f_{i + 1, j - t, k - i \times t} \binom {S_i - (j - t)} {t} \cfrac {(S_i - (k - i \times t))!}{(S_i - k) !\prod_{j = 1}^t i!} $$

第一个组合数是选择有哪些数，第二个多重排列是选择位置。

值得注意的是，如果直接枚举是 $O(n^4)$ 的，但是注意到对于 $j, t$ 都是是 $O(\frac ni)$ 的，那么减掉一些无用的状态，复杂度实际上是 $O(n^3)$ 的。

提交记录：https://atcoder.jp/contests/arc162/submissions/49158884

escape 逃跑

对于存在点权 $|w_x| \le 10^6$ 的树上，初始在 $1$，在第一次到达某个点的时候得分会加上其点权，问是否存在一种走法使得得分一直非负的情况下到达目的地。

最初都可以胡出一个假的做法，不断的找可以到达并且可以做出贡献的联通块，直到到达目的地。但是容易被 $x \to y \leftarrow z$ 其中 $x, z$ 为正，但是 $y$ 为负的情况卡掉。这种情况就是说在两边子树来回来回。

不过这提供了一点思路，考虑这种路径都会形成限制 $(lim, sco)$，只有当得分 $\ge lim$ 的时候才可以获得 $sco$ 的额外得分。发现两棵独立的子树都会对答案造成影响，但是之间不会造成影响，所以合并就可以直接揉在一起。

但是合并意味着必须经过 $y$ 这个共同的祖先，考虑其影响。

如果只是这一个节点，那么影响自然是 $(-w_x, w_x)$。但是会当 $w_x < 0$ 时自然是不好的。

所以需要利用某些对 $(x, y)$ 使得其为正。讨论是简单的，略。

见 [CERC2013] Escape

$\downarrow 2024.01.08 night$

fib 斐波那契

给定递推式 $f_0 = 0, f_1 = 1, f_n = s_{n - 1} f_{n - 1} + s_{n - 2} f_{n - 2}$，其中 $s$ 是一个满足 $s_i = s_{i \% n}$ 的序列，$n, m \le 10^5$。

给定 $s_{[0, n)}$，以及 $m$ 个修改 $s_x = v$，其中 $x \ge n$，求 $f_k, k \le 10^{18}$。

分段矩阵乘法和快速幂即可，这是简单的。

task 出题

费用流题，最后一个点卡不过去，略。

std 的代码用的是 PushRelabelMCMF，不知道是个什么写法。

swap 交换

给定一个序列，每次可以交换一个逆序对，求最终序列可能的情况数。

• 对于 $01$ 序列，$n \le 10^3$。
• 对于一个排列，$n \le 20$。

对于 $01$ 序列是简单的，设 $f_{i, j}$ 表示考虑前 $i$ 个数，最后一个 $0$ 在 $j$ 的方案数，转移是简单的，可以保证不重复。

但是这对于正解没有启发意义，考虑另外一种思考方式。

答案序列合法的充要条件为

• 从左到右第 $i$ 个位置大于等于原始序列中的第 $i$ 个 $1$ 的位置。

那么类似的设置状态就可以做到 $O(n^2)$。

于是对于一个排列，如果将 $> k$ 的设为 $1$，其他的为 $0$，那么问题又转化为了 $01$ 的问题。

于是数字从大到小考虑，每次会多出一些 $1$ 来，注意到一定是个 DAG，转移路径方案是简单的，复杂度 $O(n 2^n)$。

$\downarrow 2024.01.09$

challenge 挑战 NPC

对于一个平面图上 $n \le 100$ 个点，如果两者距离小于 $d$ 那么连边，对于 $d = 1, 2, \cdots m \le 10^5$ 求最大团。

发现对于一个距离 $d$，实际上是用一个直径为 $d$ 的圆去覆盖，看至多能覆盖多少个点。但是实际上可能并不需要这么大的直径，可以不断缩小这个圆直到最远的两个点在圆上，于是利用这个距离更新答案即可。

发现这个距离可以 $O(n^2)$ 的枚举点对进行贡献，现在问题是如何求这个团。

注意到可能存在在

红色和蓝色两个位置。并且同种颜色之间的距离一定 $\le d$。

于是发现如果对于距离 $\gt d$ 的连边，那么最终是一个二分图，注意到最大独立集 $= n -$ 最大匹配，那么跑一次网络流即可。

注意到复杂度为 $O(n^2 n \sqrt m)$ 其中 $m = O(n^2)$，所以复杂度为 $O(n^4)$，实际上远远达不到此上界，所以可过。

candy 糖果大赛

对于一个序列 $A$，每次可以选择一个 $x \in [1, \max A_i]$，令 $A_i \leftarrow A_i \bmod x$，操作使得 $A_i$ 为 $0$ 的那个人输。给定限制 $A_i \in [1, L_i]$，求这 $\prod L_i$ 个序列中先手必胜的局面数。

在考场上有这么一个乱搞的做法。首先打表，打出来发现先手必败的局面很少，所以可以考虑容斥计算必败的局面数。

将 $n \le 5$ 的必败局面打出来，发现当 $n \ge 3$ 时，必败局面满足 $A_i \equiv 0 \pmod {12}$，于是猜测之后必败的局面都需要满足这个要求，于是利用这个结论暴力枚举打表，发现在给定值域下只有 $265$ 种局面满足必败。

于是问题转化为给定每个位置的限制，将每种局面填进去的方案数，这是 $O(n^2)$ 容易求解的，于是总的复杂度为 $O(265 n^2)$。

可以严谨证明一下，首先判掉 $\{1\}, \{2\}, \{4, 8\}$ 的局面，发现当存在奇数时可以转化为 $\{1\}$，否则在 $\bmod 4$ 时可能转化为 $\{2\}$ 的局面。考虑有 $\{4, 8\}$，考虑 $\bmod 12$。

如果全部剩下 $4$ 那么可以 $\bmod 3$ 转化为 $\{1\}$，全部剩下 $\{8\}$，考虑 $\bmod 6$。那么剩下的局面就只有 $A_i \equiv 0 \pmod {12}$ 的局面了。

party 聚会

JOISC 2017 Day2 门票安排 抽象题。

二分答案是一定可以想到的。但是 check 就很难想象，此时我们可以考虑通过增加枚举量得到一个较劣的复杂度，再来优化。

观察到如果两个区间无交，但是同时翻转，那么一定不优，也就是所有翻转的区间交集 $t$ 不为空，那么我们可以枚举这个交点。但是发现此时还是不知道该怎么算答案。设 $f_i$ 表示初始被覆盖的次数，$g_i$ 表示被翻转了的区间覆盖了多少次，那么只需要一个 $cnt$ 表示翻转的区间的数量就可以知道答案。

于是再枚举一个 $cnt$，考虑贪心，如果实际覆盖次数 $s_i = f_i - g_i + (cnt - g_i) > mid$，那么不断取出左端点在 $i$ 左边，右端点最大的那个没有翻转的区间进行翻转，这样可以保证右边覆盖的最少。最后差分判断一下交集右侧是否合法即可。

现在的复杂度是 $O(n^3 \log n \log V)$，算法本身没有优化的空间了，考虑优化 $t, cnt$ 的枚举。

感性理解可以知道 $t$ 应当需要包含 $f_i$ 最大的那个点，于是只需要随便找一个作为交点即可。

由于知道了 $g_i \le \frac {f_i + cnt - mid}{2}$，知道了对于 $f_t$ 是最大的，需要 $g_i$ 尽可能大，但是 $cnt$ 尽可能小，于是猜测当 $cnt = \frac {f_t - mid} 2$ 的时候很合适，但是需要 $+1$ 微调一下。

可以考虑理性证明一下。

1. 存在 $s_t = \max s_i$ 或 $s_t = \max s_i - 1$。这比较好证明，考虑反证，如果存在 $s_t \le \max s_i - 2$，那么如果取消两个区间的翻转，使得 $s_t \leftarrow s_t + 2$，而交之外的 $\max s_i$ 不会变大，也就是答案不会更劣，所以存在该性质。

2. 存在 $f_t = \max f_i$。我们知道 $s_t = f_t - g_t$，以及一定满足的若 $i$ 不在交内，$s_i \lt f_i + g_t$。配合 $1$，于是说 $s_t + 1 \gt \max s_i \ge \max f_i + g_t$ 也就是 $f_t \ge \max f_i + 3 g_t$，考虑 $g_t \ge 0$，所以 $f_t \ge \max f_i$，于是 $f_t = \max f_i$。

根据 $1$ 可以知道 $cnt = \frac {f_t - mid}{2} + 0/1$，根据 $2$ 可知 $t$ 只需要随便枚举一个即可。

于是总复杂度为 $O(n \log n \log V)$。

$\downarrow 2024.01.12$

book 书本

简单数位 DP，略。

lottop 欧内的环

求无权平面图最小环长度，其中满足每个点的度数 $\ge 3$。

平面图的每一个面对应着对偶图的每一个点。欧拉公式说的是 $n - m + r = 2$，其中 $r$ 为面数。
考虑对于一个平面图，面的次数之和 $= 2m$，而每一个面的次数 $\ge 3$，也就是 $3r \le 2m$，带入欧拉公式，$3 \times (2 + m - n) \le 2m \to m \le 3n - 6$。

本题在对偶图中，由于 $\sum deg = 2m \le 6n - 12$，也就是至少存在一个点度数 $\le 5$，于是原图中至少存在一个 $\le 5$ 的环。考虑每个点度数 $\ge 3$ 保证了环的存在。

于是我们只需要判断 $3, 4$ 元环是否存在即可。

rotate 旋转迷宫

考虑变成置换来判断，这是简单的，考虑如何操作可以交换相邻的两项，这是可以枚举的。

于是就完了。

$\downarrow 2024.01.12$

shark 鱼鱼枕

有 $n \le 10^5$ 堆鱼鱼枕，每次可以整体 $-1$，也可以取走最大的那堆，最终取完了所有的人输，判断先手胜负状态。

两种做法。

• 抽象 DP。将 $A_i$ 从小到大排序，考虑初始局面为 $(n, A_n)$，也就是至多 pop $n$ 次，至多整体 $-A_n$，考虑两种操作，如果是 pop，那么使得二元组 $-(1, A_x - A_{x - 1})$，如果是整体减，那么为 $-(0, 1)$。考虑设 $SG$ 函数 $f_{x, y}$，那么转移为：

$$f_{x, y} = !f_{x, y - 1} | !f_{x - 1, y - D_x} $$

归纳发现实际上是一些 $101\ldots1$ 的区间拼接一起，对于 $D_x$ 分奇偶讨论即可维护。注意 $y \le 0 \to f_{x, y} = 1$

• 还是抽象状态，如果 pop 则 $x + 1$，否则 $y + 1$，那么如果越过了 $(n, A_n)$ 的边界就会挂。归纳可以发现在 $y = x + k$ 上的状态都是一样的，讨论即可。

eert 寸又木

首先 $S_1$ 会形成若干内向树，我们把这些点缩起来。

如果 $x$ 不能够接在 $y$ 下面，当且仅当对于 $\forall z \in T(y)$ $x \to z$ 都被 ban 掉了。

于是新图可以简单建出来，考虑构造如何接在一起。不难有一个 $O(n^2)$ 的做法，从每个点开始 bfs，看是否能够到达所有点。

考虑标记不清除，如果在 $x$ 开始 bfs 后使得所有点被访问到了，那么 $x$ 一定可以作为根，否则无解。可以这样考虑，首先 $\lt x$ 的都不可能成为答案，而 $x$ 访问到了所有 $\gt x$ 的，如果 $y \gt x$ 可以作为答案，由于 $x$ 可以到达 $y$，所以 $y$ 一定也可以作为答案。

考虑边数实际是 $O(n^2)$ 的，但是考虑只有 $O(k)$ 条被 ban 了的边，那么建出补图跑即可。

xmas 圣诞

不会，暂咕。

$\downarrow 2024.01.13$

sort 排序

给定排列 $[0, n)$，每次可以 $\mathrm{swap}(P_x, P_{x + P_x})$，构造一个 $O(n^2)$ 的做法排序这个排列。

cout << n * n << '\n';
for (int i = n - 1; ~i; --i)
	for (int j = 0; j < n; ++j) cout << i << ' ';

正确性很简单。

ds DS

IOI 2021 分糖果。

对于询问做扫描线，也就是从 $i = 1 \to n$ 维护影响 $i$ 的有那些操作。

先不考虑上下界，这是好维护的，线段树即可维护出 $A_i$ 在 $1 \to m$ 的序列 $B_i$。通过神秘的讨论可以知道如果同时碰到上下壁的充要条件为 $\max B_{[k, m]} - \min B_{[k, m]} \le T_i$。

如果不满足，那么只会碰到下壁，利用 $\min B_{[0, m]}$ 是容易处理的。

我们可以二分出一个最大的 $k$ 满足上述条件，那么在 $k$ 操作之后，必定碰到了某个界，并且之后不会碰到另一个界。分 $B_k = \max B_{[k, m]}$ 或者 $B_k = \min B_{[k, m]}$ 讨论即可。

count 数数

定义简单排列为所有置换长 $\le 2$ 的排列。计数长度为 $n$ 的恰有 $k$ 个逆序对简单排列，模 $2$。

看到 $\bmod 2$ 考虑构造双射将一些情况干掉。

考虑 $inv(P) = inv(P^{-1})$ 的性质，知道如果 $P \ne P^{-1}$，那么对于答案不会有影响，而如果 $P = P^{-1}$，则必定满足所有置换环长 $\le 2$。于是问题转化为计数长度为 $n$ 的恰有 $k$ 个逆序对排列。

见 对于 EI K 逆序对排列计数的另一种自然求和方法的理解。本题中可以利用 bitset 使得复杂度为 $O(\frac {k \sqrt k} w)$。

$2024.01.15$

duck Giao 徽的烤鸭

对于一棵树，每个点有点权，如果选择了这个点那么花费 $-w_x$。设 $k_x$ 表示最大的 $k_x$ 使得对于所有 $d(x, y) \le k_x$ $y$ 都被选择，那么获得 $v_x$ 的收益。求最大的收益。

一个简单的想法是 $O(n^3)$ 的网络流，然而边数和点数都是 $O(n^2)$ 的，空间会被卡。

考虑一个 $O(n^2)$ 树形 $DP$，设 $f_{x, i}$ 表示只考虑 $x$ 的子树，距离 $\le i$ 的全选的最大价值，那么 $f_{x, i} = \sum f_{y, i - 1}$，最后求一个后缀 $\max$ 即可。

dance A Dance of Fire and Ice

给定一些初值，在 $\bmod p$ 意义下每次可以 $\times A_i$ 或者不操作，求最终可以得到那些数。保证 $p$ 是质数。

利用原根将 $\times A_i$ 变成 $\times g^{k}$ 从而变成指数加法是简单的。

于是有一个 $O(\frac {p^2}{w})$ 的做法，但是这里 $n \le 2 \times 10^5$，4s 险过。

注意 bitset 的 count 操作不是 $O(\frac n w)$ 的，而是 $O(\frac n w w) = O(n)$ 的！

考虑每次实际上是令一个 $f_{x} = 1, f_{x + k} = 0$ 的位置变化，那么可以通过二分和哈希找到这个位置，复杂度是 $O(p \log^2 p)$ 的。

注意到 $f_{x} = 0, f_{x + k} = 1$ 的位置和满足上述的位置的个数的相同的，于是直接二分只是多了一个 $2$ 的常数。

excavator 挖掘机技术哪家强

给定一个序列，初始 $A_i = i$，每次交换相邻两项并连边，求最大团大小。

注意到最大团 $=$ 补图的最小独立集，考虑在本题中，如果补图中 $a \lt b \lt c, a \to b, b \to c$，那么一定存在 $a \to d$。也就是如果边定向为从小的连向大的，那么是一个已经完成了传递闭包的 DAG，可以直接跑最小链覆盖的匹配。

然而是 $O(n^2)$ 的，考虑优化。

注意到 $n -$ 匹配数是答案，而答案是 $O(\sqrt m)$ 的，也就是不会被匹配的点有 $O(\sqrt m)$ 个，那么我们可以先贪心的把所有能直接匹配的匹配掉，然后再进行增广。

这样复杂度大概是 $O(n \sqrt m)$ 的，严谨的证明不太明白。

$\downarrow 2024.01.16$

coins 硬币

多组询问，每次给定 $n \le 10^6$，求 $n^2 + 1$ 的最小质因子。

两种做法。

1. 类似于埃氏筛的做法，从 $i$ 开始，必定的是 $v_i$ 是个质数，并且 $v_{i + k v_i}$ 都是 $v_i$ 的倍数。这是容易证的。
2. 二次剩余，注意到 $x^2 + 1 \equiv 0 \bmod p \to x^2 \equiv p - 1 \bmod p$，考虑 $p$ 一定是质数，于是利用原根，那么 $x^2 \equiv g^{\frac {p - 1}{2}} \to x \equiv g^{\pm \frac {p - 1}{4}}$，如果 $4 \nmid p - 1$，那么一定无解，否则有两个原根，则可以调和级数枚举。

guess 猜数

你要从数集 $\{1, 2, \ldots, n\}$ 中猜一个数，每次提问一个数 $x$，交互器会返回大于、小于或等于，代价是 $x$。
定义 $C(n)$ 表示在最优策略下的总成本。最优策略指的是在最坏情况下最小化总成本的策略，求 $\sum_{i = 1}^n C_i$。

刚开始会有一个错误的 DP，考虑：$f_{i, j}$ 表示 $i$ 个数询问 $j$ 次的最小代价，转移是简单的。但是假了，考虑这里实际上是询问 $\le j$ 次，但是在加入了 $x$ 的限制之后，最优的方案是会变化的，也就是不一定还是最优的，所以挂。

考虑 $O(n^3)$ 的区间 DP，$f_{l, r} = \min \{ \max(f_{l, k - 1}, f_{k + 1, r}) + k \}$。利用优先枚举 $r$，再枚举 $l$ 再利用单调队列可以做到 $O(n^2)$，然而还是过不了。

神秘的结论是 $k$ 的范围是 $O(\frac n {\log n})$ 的，所以可以优化到 $O(\frac {n^2}{\log n})$，需要注意缓存的问题。

card 卡片

你有若干张编号为 $1$ 到 $n$ 的卡片，和 $m$ 包可以无限开的卡包，你可以以任意顺序执行任意多次以下操作:
• 将 $2i$ 张编号为 $i$ 的卡片换成一张编号为 $i \bmod n + 1$ 的卡片。
• 选择一个卡包打开并获得其中的所有卡片。
你希望你拥有的卡片张数尽可能的少，你需要求出经过任意多次操作后你拥有的卡片的最小张数。

一个显然的想法是先全部转化为第一种卡牌，也就是向前转换。

设 $F_n = 2n F_{n - 1}$，那么 $1$ 张 $i$ 牌可以转化为 $F_i$ 张 $1$ 牌，于是整个序列都可以映射为一个数。

考虑这里卡包是无限的，所以可以凑出 $g = \gcd(F_n - 1, T_i)$ 的倍数，其中 $T_i$ 是某个卡包对应的卡牌数。

于是可以暴力的枚举 $S + kg$ 判断答案。注意到 $F_n$ 张 $1$ 可以转换为 $1$ 张 $1$，所以放在 $\bmod F_n$ 下即可。

但是这样是 $O(\frac {F_n}{g})$，当 $g$ 很小的时候显然会挂，考虑是否存在 $O(g^2)$ 的做法。

考虑每次实际上是可以加一张大小为 $F_i$ 的牌，最终需要凑到某个 $S \bmod g$ 的局面，考虑 $dis_x$ 表示凑到 $x \bmod g$ 的最小张数，那么跑一个同余最短路即可。

SMB 提出分层同余可以优化常数。

$\downarrow 2024.01.18$

tree 树上横跳

这棵树每条边有边权。但每次只能从一个节点 $x$ 跳到它的子孙 $y$，代价为 $x \times dis(x, y)$。多次每次询问两个点 $x, y$，是否能从 $x$ 到 $y$，如果能到则最小代价为多少。

先考虑一个傻逼的想法，转换为 $x \times (dis_y - dis_x)$，于是就是一个斜率优化的问题，那么就无法做了。

但是发现实际上可以贪心，每次跳到第一个比自己小的，分段，那么将衍生出三种做法。

1. 我的做法，将边拆贡献，于是问题转化为子树取 $\min$，链求和问题，容均摊即可。
2. 拆单调栈的做法，放在线段树上，分为 $O(\log n)$ 的单调栈，每次二分断点。
3. 做法 $2$ 实际上是兔队线段树，所以可以通过可持久化的方式维护，查询即可。
4. 类似于树的重心跳重链的做法，这里可以类似的，预处理出单调栈的下一个，然后在重链上倍增跳，切链时改变即可，复杂度 $O(n \log^2 n)$。

price 定价

考虑一个简单的贪心。

每次自然的将最大的不合法的位找出，并将最小的可以设为 $1$ 但是非 $1$ 的位设为 $1$ 并将之后的 $1$ 全部消除。

考虑这里 $O(1000q) \sim 3 \times 10^8$，所以可以如此暴力。

如何暴力，也就是不断的双指针即可。

graph 难题

给定无向图，每条边有两种权值 ，对于 $k \in [1, n)$ 计算出选出恰好 $k$ 条不
成环的边，让这些选出的边 $(\sum A_i) \times (\sum B_i)$ 最小。

傻逼题。先考虑一个 $O(m^3 \log m)$ 的做法，也就是最小乘积生成树的 quick hull 做法。

但是显然会 TLE，考虑一个新的做法。

考虑实际上有多少种排序的方式？类似先前的各个题，实际上的排序只有 $O(m^2)$ 种，因为每次按照 $x + ky$ 的方式，意味着只有 $k = \frac {\Delta x}{\Delta y}$ 的时候才会有相对顺序的改变。

那么考虑每次交换两个相邻的位置 $i, i + 1$，可以分为如下几种情况：

• 对于 mst 没有影响，那么只会影响 $O(1)$ 个位置的前缀，直接更新答案即可。
• 交换 $i, i + 1$ 出现原本都在，但是交换后之后 $i$ 在了的情况，这就需要暴力重构这 mst。暴力重构是简单的，但是考虑如何判断是否存在这种情况。
  • 题解说用 LCT，或者暴力上树剖。解题人说可以利用并查集简单实现。

题解证明了第二种情况出现次数是 $O(n \sqrt n)$ 的，证明规约很抽象，暂且不谈。

所以总复杂度是 $O(n^2 \log n + n^2 \sqrt n)$。

$2024.01.19$

div 整除

求有多少个正整数 $x$ 满足 $\sum_{i = 0}^{n - 1} c_i x^{a_i}$ 能被 $\sum_{i = 0}^{m - 1} x_i$ 整除，其中 $a$ 和 $c$ 是两个给定的序列。

特判掉 $x = 1$ 的情况。考虑将后者变为 $\frac {x^m - 1}{x - 1}$，那么问题为求满足：$(x - 1)\sum_{i = 0}^{n - 1} c_i x^{a_i} \equiv 0 \pmod {x^m - 1}$ 的那些 $x$。

那么发现 $a_i$ 需要对于 $m$ 取模。

首先答案在 $O(n)$ 级别，因为每次 $-(x^m - 1)$ 使得所有系数 $-1$，但是操作了 $x$ 次之后，相当于只操作了 $1$ 次，由于系数是 $O(n)$ 的，所以答案是 $O(n)$ 的。

至于判断，注意到利用进位，那么最终如果 $\equiv 0$，那么要么全部 $= 0$ 或者 $x - 1$ 或者 $1 - x$，也就是 $1, -1$ 的情况。

注意到减少的次数是 $O(\frac n x)$ 的，那么合起来 $O(n \log n)$，随便维护即可。

dictionary 词典

令 $H(x) = \sum_{i = 1}^x 1 + \lfloor \log_2 i \rfloor$，求 $F(n)$，其中 $F(n)$ 满足递推式：

$$F(n) = \min(F(i) + H(i)[i \gt 1] + F(n - i) + H(n)) $$

注意到 $H$ 是单调的，或者说是凸函数，那么 $F$ 自然也是单调的，或者说凸函数。

那么容易得到一个 $O(n)$ 的双指针，或者 $O(n \log n)$ 的二分。

现在我们需要做到亚线性。考虑差分数组，容易发现是连续且值域为 $O(\log^2 n)$ 的，于是尝试利用差分数组求解。

每次可以 $1.5$ 的倍增，求出 $F(x) - F(x - 1)$，据此得出下一个差分的数的出现位置。

注意获取一个已知的数是 $O(\log n)$ 的，未知的是 $O(\log^2 n)$ 的，套上二分/倍增是 $O(\log^3 n)$，值域是 $O(\log^2 n)$ 的，所以总复杂度是 $O(\log^5 n)$，非常抽象。

$\downarrow 2024.01.20$

delegation 每日委托

给定 $n, m$，求 $1 \le x \le n, 1 \le y \le m$ 满足 $xy$ 为完全平方数的有序对 $(x, y)$ 的数量。

类似于 P5438 【XR-2】记忆 的做法，最终的式子为：

$$\begin{aligned} f(n, m) &= \sum_{x}^{\min(n, m)} \mu^2(x) \left \lfloor \sqrt {\frac nx} \right \rfloor \left \lfloor \sqrt {\frac mx} \right \rfloor \\ S(n) &= \sum_{i = 1}^n \mu^2(i) = \sum_{i = 1}^{\sqrt n} \mu(i) \left \lfloor {\frac n {i^2}} \right \rfloor \end{aligned} $$

注意到对于第一次整除分块，状态数是 $O(\sqrt[3]n)$ 的，因为要么 $i \le \sqrt[3]n$，要么 $\left \lfloor \sqrt {\frac ni} \right \rfloor \le \sqrt[3]n$。

对于第二次整除分块，状态数也是 $O(\sqrt[3]n)$ 的，所以 $O(\sqrt n)$ 的把 $\mu (i)$ 筛出来直接做复杂度是 $O(n^{\frac 7 {12}})$ 的，因为当 $i \ge \sqrt{\min(n, m)}$ 时，第一次整除分块大概只有 $O(\sqrt[4]n)$ 种取值，在 $10^{15}$ 差不多能过，但是 $10^{17}$ 就略慢了。

然而如果将预处理的部分设为 $n^{\frac 37}$，溢出的部分用杜教筛，那么复杂度就变为 $O(n^{\frac 37})$ 了，考虑证明。

首先考察对于 $S(n)$ 的整除分块的做法，对于 $\le M$ 的部分预处理，其他地方整除分块做，考虑这部分在第一次中剩下的为 $O(\sqrt{\frac nM})$ 种，设 $v = \sqrt {\frac n i} \le \sqrt \frac nM \to i \le \frac {n}{v^2}$，那么复杂度的计算式子为：

$$\begin{aligned} \sum_{v = 0}^{\sqrt {\frac nM}} \left(\frac {n}{v^2} \right)^{\frac 1 3} & \sim \int_{0}^{\frac nM} \left(\frac {n}{v^2} \right)^{\frac 1 3} \mathrm{d} v \\ & = n^{\frac 1 3} \int_0^{\sqrt \frac nM} v^{\frac {-2}3} \mathrm{d} v \\ & = \left. \frac {1}{3} n^{\frac 1 3} v^{\frac 13} \right \vert_{0}^{\sqrt \frac nM} \\ & = \frac 1 3 n^{\frac 1 2} M^{-\frac 1 6} \end{aligned} $$

考虑实际复杂度是 $O(n^{\frac 1 2} M^{-\frac 1 6} + M)$，所以当 $M = n^{\frac 3 7}$ 时取得理论最佳复杂度 $O(n^{\frac 37})$。

第一次整除分块的复杂度还是 $O(\sqrt[3] n)$ 的，这不是复杂度瓶颈。后面的计算复杂度在上面给了估计，考虑杜教筛部分的复杂度。

注意有对于一个 $S(t)$，需要利用杜教筛的位置为 $\left \lfloor \sqrt \frac ti \right \rfloor$，对于 $f(n, m)$ 需要用到的 $t$ 的位置为 $\left \lfloor \frac n {x^2} \right \rfloor$，也就是位置为：

$$\begin{aligned} \left \lfloor \sqrt {\frac n {x^2 i}} \right \rfloor = \left \lfloor \frac {\sqrt {\frac ni}}{x} \right \rfloor \end{aligned} $$

注意到实际上杜教筛 $S(n)$ 会筛出所有 $S(\left \lfloor \frac ni \right \rfloor)$，类似的设预处理的上界是 $M$，实际上杜教筛的复杂度大概为：

$$\begin{aligned} \sum_{i \le \frac {n}{M^2}} \left(\sqrt \frac ni \right)^{\frac 23} & \sim \int_0^{\frac n {M^2}} \left(\sqrt \frac ni \right)^{\frac 23} \mathrm{d} i \\ & = \frac 3 2 n^{\frac 13} \left. i^{\frac 23} \right\vert_0^{\frac n {M^2}} \\ & = \frac 32 n M^{-\frac 43} \end{aligned} $$

实际上复杂度为 $O(n M^{-\frac 43} + M)$，那么当 $M = n^{\frac 37}$ 时取得最优复杂度 $O(n^{\frac 37})$。

所以总复杂度为 $O(n^{\frac 37})$。

$\downarrow 2024.01.23$

lol 午夜后的棒棒糖

给定序列 $a$ 计数满足条件的有序三元组 $(A, B, C)$ 的个数。

$$\begin{cases} A, B, C \subseteq \{1, 2, \ldots, n\} \\ A \cap B = B \cap C = C \cap A = \emptyset \\ \text{xor}_{i \in A} a_i = \text{xor}_{i \in B} a_i= \text{xor}_{i \in C} a_i \end{cases} $$

很难注意到可以构造双射，发现 $(A, B, C)$ 和满足 $\bigoplus_{i \in S} a_i = 0$ 构成的集合的有序对之间一一对应，那么异或和为 $0$ 的子集个数为 $k$，答案为 $k^2$。

怎么求呢，考虑线性基，每次如果不能成功加入，那么个数 $\times 2$。

lct 元素反应

计数满足 $dis(x, y) \le \max(dis(x, z), dis(y, z))$ 的三元组的个数。

傻逼题。

$\downarrow 2024.01.24$

split 划分

对于一个长度为 $2n$ 的排列，定义它的权值为在所有将其划分成两个不交的长度为 $n$ 的子序列 $\sum a_i b_i$ 的最大值。
现在定义 $M$ 为所有排列的权值的最大值，求有多少个排列可以取到这个最大值。

注意到匹配一定是形如 $1 - 2, 3 - 4$ 这般这般的，那么考虑能匹配当且仅当左右形成了一个合法的括号序列，那么就是 $C_n$，考虑左部点有哪些，右部点怎么排，得到 $n! 2^n$ 的系数。

cut 切割

给定一个长度为 $2n$ 的序列。定义一次操作为选择一对相邻且不同的数，将它们删除并将两侧合并成一个新序列。计算有多少将这个序列分段的方案，使得每一段都可以通过操作删除至空。

考虑一个序列可以被删空的充要条件是没有绝对众数，考虑对于每一个数个数前缀和 $(r - l) \ge 2(s_r - s_l)$ 便是合理的，也就是当 $2s_l - l \ge 2s_r - r$ 的 $l$ 对于 $r$ 都没有贡献。

于是一个 naive 的 $O(n V \log n)$ 的东西就出来了。

考虑到 $2 s_i - i$ 变化量是 $\pm 1$，那么实际上有用的 $i$ 只有 $O(\sum cnt_x) = O(n)$ 个，找出来这些位置在上面一种方法的基础上剪枝即可做到 $O(n \log n)$ 带个大常数。

$\downarrow 2024.02.13$

青蛙干饭 froggay

两种做法：

• 暴力记搜，加上倍增优化向前航行的过程，可以过，复杂度不会证。
• 分治，考虑每一条航线会怎么走，递归下去，复杂度 $O((n + m) \log n)$。

第二种不太清楚。

原题：https://loj.ac/p/2399

shaber 赛博航行

给定 $a_i \in [-1, 1]$，每次可以区间前后缀和，或者全局取反，求最小操作次数使得任意 $a$ 非负。

答案一定 $\le 3$，考虑可以如下构造：

• 找到前缀最大和最小的位置，如果最大的在后面，那么取反。
• 在最大的后面一次前缀，然后全体后缀。

那么只需要判断 $0/1/2$ 即可，操作两次分类讨论：

• 取反然后一次后缀/前缀。
• 两次前缀，两次后缀。第二次全局不劣。
• 一次前/后缀和一次后/前缀。第二次全局不劣。

glaph 考拉的图

定义集合 $S$ 的权值 $f (S)$ 为使得 $S$ 中所有点连通至少需要在 $T$ 中留下的边
数，请你求 $\sum f(S)^k$。

一个关于 $n^m$ 的斯特林等式：

$$n^m = \sum {m \brace i} \binom ni i! $$

其实就是：

$$n^m = \sum {m \brace i} n^{\underline{i}} $$

由于我一直写的第二种，所以反应不过来。

那么目标是求：

$$\sum {k \brace i} i! \sum \binom {f(S)} i $$

后者实际上是在每个虚树种选出 $i$ 条边的方案数，记为 $S_i$。

考虑 $f_{x, i}$ 表示 $x$ 作为虚树的最高点的方案数。

这像一个树上背包，考虑转移：

$$f_{x, i + j} = \sum f_{x, i} f_{y, j} $$

考虑到父亲这条边可选可不选，但是不选的时候不能只有一个子树内有边，所以需要：

$$\begin{aligned} f_{x, i} &= f_{x, i} + f_{x, i - 1} \\ S_i &= S_i - f_{x, i} \\ \end{aligned} $$

背包复杂度 $O(nk)$

$\downarrow 2024.02.15$

match 一般图带权多重匹配

给定 $n \le 50$ 个数，其中 $k \le 8$ 个奇数，可以花费 $c_{i, j}$ 的代价使得 $a_i, a_j$ 各减 $1$，求将序列全变成 $0$ 的最小代价。

看到 $k$ 很小，考虑 $k = 0$ 的时候怎么做。

看上去很费用流，而这种问题需要二分图，考虑到其实有偶数，所以把偶数变成两半，那么就是一个二分图跑费用流的问题了。

考虑奇数，上面做的事情无非是用一半来消，一半来被消，所以 $\binom {2k} k$ 的枚举一半多的哪一点在哪边即可。

复杂度大概是 $O(\binom {2k} k n^3)$ 的。

sort 排序

给定 $1$ 根树。每一个叶子节点可选一个权值，父节点的权值序列由儿子节点的权值以某种顺序连接而成。每个父亲不超过 $k \le 8$ 个儿子。构造方案使得 $1$ 号点的权值序列递增，或者说明无解。

将值域离散化，考虑一个 $O(n m k!)$ 的 DP，设 $f_{x, i}$ 表示权值序列最大值 $\le i$ 的最小值最大为多少，那么转移自然是：

$$f_{x, i} = f_{y, f_{x, i} - 1} $$

利用状压搞定状态就是 $O(nm 2^k)$ 的了。

后面的 $O(2^k)$ 是不能再减了，考虑前面可不可以减下去。

值得注意的是 $f_{x, i}$ 有用的右端点个数很少，记为 $cnt_x$，在一次合并之后端点个数至少减少为 $\min(cnt_x, cnt_y)$，意味类似启发式合并的东西是合理的。

但是注意到合并有顺序，所以合并的时候像 DP 的时候一样离散化再开一个数组合并，这样复杂度是 $O(k 2^k \sum cnt_y)$ 的，最终出来的状态数是 $O(\min cnt_y)$ 的。

不妨设叶子数为 $d$，那么有用的合并次数为 $d - 1$ 次，每次如果卡满，那么每一个的 $cnt$ 应该是 $\frac m d$，要将 $2^k$ 卡满，那么需要合并的节点数是 $O(\frac d k)$ 的，也就是总的复杂度大概就是：$O(\frac dk k 2^k 8 \frac md) = O(2^k m)$ 。可能中间离散化之类的会多带个 $O(\log n)$ 什么的，问题不大。

infect 传染

给定树，每个节点可以感染 $R_x$ 以内的节点，并且可以链式传递。求最初最少感染几个节点可以传染所有节点。

一个 $O(n^2)$ 做法是对于每一个节点向能影响到的节点连边，然后跑一个 tarjan，求缩点后入度为 $0$ 个点的个数即可。

考虑优化建图，与 $dis$ 相关考虑边分治，搞一个前缀优化即可。

注意卡空间，所以图要重复利用，没用的边能砍就砍，做到 $O(n \log n)$ 空间，$O(n \log^2 n)$ 时间。

$\downarrow 2024.02.15$

tetris 俄罗斯方块

给定 $n \le 20$ 的偏序关系，多次询问求 $P$ 作为子段的合法拓扑序个数。

首先考虑 $f(S)$ 表示只考虑 $S$ 内的元素合法的拓扑序个数，每次枚举最后一个元素是啥，这样就可以 $O(2^n)$ 求出拓扑序个数。

但是加上子段呢？考虑一定会有前面一段和后面一段，考虑 $f(S)$ 求的过程实际上不断推的是前缀，另记一个 $g(S)$ 类似的考虑是后缀。

于是对于一个集合 $S$ 的答案类似于：

$$\sum_{T \subseteq U - S} f(T) g(U - S - T) $$

这是子集卷积，$O(3^n)$ 显然过不了，那么套模板即可 $O(n^2 2^n)$。

但是可以不用子集卷积，考虑如果确定了 $S$，那么前面存在必选的一些元素，后面同理，不妨记为 $A, B$，那么剩下 $C$ 元素两边都可能，考虑枚举 $C$ 的子集，那么答案为：

$$\sum_{T \subseteq C} f(A + T) g(B + C - T) $$

在极限数据下也卡不满，可以如下粗略的估算上界，不妨将极限情况更极限，变成 $20$ 个点两两配对的情况，这样限制是最少的。

那么对于 $|S| = k$ 来说，大概枚举一下内部有多少对，在考虑外部子集的个数：

$$\sum_i \binom {10} i 2^{20 - 2k - 2i} = 2^{-2k} \left(\sum_{i} \binom {10}i 4^{i} \right) = 2^{-2k} 5^{10} $$

对于每个 $k$ 求和，是 $O(5^{10}) \approx 10^7$ 的，这绰绰有余，并且实际上界是小于它的。

punch 天天爱打卡

给定若干线段，每次给定 $l, r$，求满足 $l \le l_i \le r_i \le r$ 的线段的并集大小，$1 \le l, r \le m \le 10^5$。

一个 naive 的想法是从右向左扫描线，考虑每个点被覆盖的最右端点是谁，相当于一个区间取 min。

于是简简单单的来一个 $O(n \sqrt {n \log n})$ 的分块即可过。

但是可以 $O(n \log^2 n)$，考虑需要完成的两个操作：

• 区间 $[l, r]$ 取 $\min (r, v_i)$
• 区间 $[l, r]$ 求 $v_i \le r$ 的个数。

注意到区间求实际上可以转化为全局求，因为对于 $l_i > r$ 的线段，其 $r_i$ 一定 $> r$，不会对答案造成影响，而没有被操作到的东西初始值都是 inf，所以没有影响，那么区间自然就可以全局。

那么就可以容均摊 $+$ BIT 维护即可，复杂度 $O(n \log^2 m + q \log n)$。

存在 $O(n \log n)$ 的做法，但是比较神秘。

tree 树上距离

给定一棵树，求对于所有排列 $P$，$\sum dis(P_i, P_{(i + 1) \bmod n})$ 的最小值。

首先会有一个 $O(n^3)$ 的想法，考虑一个子树内会合并成若干个贡献的段，并且不同的子树在当且节点可能会合并：

$$f_{x, i + j - t} = \max t \times w_e + f_{x, i} + f_{y, j} (t \in [0, 2 \min(i, j)]) $$

考虑优化，对于 $f_{x, i} + f_{y, j}$，可以贡献到的地方是：

$$\to f_{x, z}, z \in [i + j - 2\min(i, j), i + j] $$

注意到如果分讨了 $i \le j$ 和 $i > j$ 的情况，那么就是一个单调队列优化的问题，复杂度变成 $O(n^2)$。

正解说 $f_{x, z}$ 是一个凸函数，那么合并是 minkowski，总复杂度 $O(n \log^2 n)$，不会。

$\downarrow 2024.02.16$

permutation 排列

定义一个排列的贡献为：

$$f(P) = \left(\sum_{1 < i < n} [a_{i - 1} > a_i][a_i < a_i]\right)^k $$

求 $\frac{\sum_P f(P)}{n!}$。

首先有一个 $O(n^2)$ 的 DP：

$$f_{n, k} = (n - 2k) f_{n - 1, k - 1} + (2i + 2) f_{x - 1, i} $$

考虑所求是：

$$\sum i^k f_{n, i} = \sum_i {k \brace i} i! \sum_x \binom xi f_{n, x} $$

设 $g_{n, i} = \sum_x \binom xi f_{n, x}$，通过一系列神秘的变换，可以推出：

$$g_{n, i} = (n - 2i) (g_{n - 1, i - 1} + g_{n - 1, i}) $$

于是可以 $O(nk)$ 求。

$\texttt{stO The\_Last\_Candy Orz}$ 给出了另外一种思考方法。

考虑所求是：

$$\sum {k \brace i} i! \sum_P \binom {f(P)}{i} $$

考虑 $g_{n, k}$ 表示 $n$ 个数，选了 $k$ 个波谷的方案数，那么：

$$\begin{cases} 2 g_{n, k} &\to g_{n + 1, k} \\ (n - 2k - 1) g_{n, k} &\to g_{n+ 1, k}, g_{n + 1, k + 1} \end{cases} $$

于是可以 $O(nk)$ 求出。

但是最后为什么答案多 $\times 2$ 了最终还是不得而知。

$\downarrow 2024.02.17$

gcd 海纳百川

给定一个长为 $n$ 的正整数序列 $a$，定义一个序列的权值为它的 $gcd > 1$ 的非空子串数量。
你可以选择 $a$ 中的任意一个数 $a_i$，将其修改为任意一个 $\le 5 \times 10^5$ 的正整数 $x$。求所有可能得到的序列权值最大值。

考虑如果没有值域的限制，那么一定是变成相邻两个数的 $\rm lcm$ 最优，但是有了值域的限制，就需要枚举用什么因数比较好。

考虑修改之后需要考虑的贡献：

• 修改点作为端点的贡献。
• 修改点作为中间点被跨过的贡献。

第一种贡献是好求的，而第二种贡献只与 $\gcd(a_{i - 1}, x, a_{i + 1})$ 有关，所以先枚举这个 $\gcd$，然后再枚举两边是个啥，统计贡献即可。

复杂度 $O(\text{能过})$。

xor 美食家

给定 $n \times n$ 矩阵，求 $\bigoplus A_{i, P_i}$ 本质不同的值的个数，$n \le 60, V \le 2^{12}$。

不妨将 $A_{i, P_i}$ 变成一个形式幂级数，那么所求即是：

$$\sum_{P} \bigoplus A_{i, P_i} $$

系数不为 $0$ 的地方。

注意到我们并不关心系数到底是个啥，只要有就行，考虑变成：

$$\det = \sum_P (-1)^{\pi(P)} \bigoplus A_{i, P_i} $$

显然的是，如果原本为 $0$ 的地方，$\det$ 出来一定为 $0$，而不为 $0$ 的地方，大概率 $\frac n p$ 是不为 $0$ 的，所以很合理。

但是直接求 $\det$ 比较抽象，考虑先 FWT 将 $\bigoplus$ 变成点乘，于是幂级数各位独立，于是可以 $O(n^3 V)$ 跑，然后 IFWT 回去即可。

复杂度 $O(n^3 V + n^2 V \log V + V \log V)$。

count 另一位面

求有多少序列 $A$ 满足：

• $\sum_i k^{A_i} \le k^n$
• $A_i \le A_{i + 1} \le A_i + 1$
• $A_1 = 0, A_m = n - 1$

注意长度没有限制。

我开始有一个傻逼的想法，考虑 DP：

$$f_{i, c} \to f_{i + 1, \left\lfloor \frac {c + x} k \right\rfloor} $$

求 $f_{n, 0}$ 然后成功炸掉。

顺着抽象，考虑可以倒着来：

$$f_{i, c} \to f_{i - 1, (c - x) k} $$

求 $f_{n - 1, k}$，瞬间就炸开了！甚至转移都不一样了。

知道了 $f_{0, c} = c$，考虑每次的转移，一个类似于前缀和的东西，考虑到单位根反演，那么实际上次数还是只会 $+1$，也就是说 $f_i$ 是一个 $i + 1$ 次多项式！

那么考虑插值即可，复杂度 $O(n^3)$，考虑加上快速插值与多点求值，复杂度 $O(n^2 \log^{2} n)$，很难过 $8 \times 10^3$ 的点，但是实际上利用差分插值的小常数做法可以过 $10^3$ 的点，在得分上足够优秀。

$\downarrow 2024.02.18$

BLRINK

在一条长度为 $n$ 的线段上均匀随机选取 $l$ 个点，将线段划分为 $m + 1$ 段。计算每一段长度都不超过 $l$ 的概率。

问题转化为如下：

• 给定 $m + 1$ 个值域在 $(0, n)$ 的随机实数变量，满足 $\sum b_i = n$，求全部 $\le l$ 的概率。

考虑到如果前 $m$ 个变量已经确定，那么最后一个变量就确定了，那么总概率空间大小为：$n^m$。

类似与在转换欧拉数到 $(0, 1)^n$ 的做法，利用容斥：

$$\sum_k \binom {m + 1} k \Big(\max(n - kl, 0)\Big)^m $$

于是答案也就显然了。

Heavensdoor

给定若干字符串，设 $M(s, t)$ 表示 $t$ 在 $s$ 中出现的次数，求：

$$\sum_i \sum_j \sum_k \sum_x \sum_y \sum_z M(s_i + s_j + s_k, s_x + s_y + s_z) $$

首先时空都是 $O(n^2 |S|)$ 是简单的，$\Sigma = \{a\}$ 也是简单的。正解与这俩无关。

考虑一个简单匹配的 DP：$f_{x, y, 0/1, i, j}$ 表示现在匹配了 $x$ 个 $s$，$y$ 个 $t$，当前多出来的这个东西是 $s$ 或者 $t$，是 $s_i$，匹配完了前 $j$ 个字符。

然后有两个转移：

$$\begin{cases} f_{x, y, 0/1, i, j - k} \to f_{x(+1), y(+1), 0/1, i, j} & \text{if } s_{i}[j - k + 1:j] = s_z \\ f_{x, y, 0/1, i, j} \to f_{x(+1), y(+1), 1/0, k, l} & \text{if } s_{k}[:l] = s_i[j + 1:] \end{cases} $$

前者可以在 AC 自动机上暴力跳，后者实际上是在 fail 树上子树加。

前者的复杂度是 $O(|S| \sqrt{|S|})$ 的，后者是 $O(|S|)$（精细实现）或者 $O(|S| \log |S|)$ 的。

$\downarrow 2024.02.20$

game 游戏

每次操作，操作者需要从三个数中选择两个数 $x, y$，把他们修改为整数 $x′$ 与 $y′$，满足 $x + y = x′ + y′$ 且 $|x − y| > |x′ − y′|$。不能操作者输。

对于给定序列，求所有有序三元组 $(i, j, k)$ 满足 $(a_i, a_j, a_k)$ 使得先手必胜的局面数。

首先对于有序的 $(x, y, z)$，变成 $(0, y - x, z - x)$ 不影响，那么用 $(0, x, y)$ 表示。

考虑当 $x > 1$ 且 $x \ne y$ 时，显然可以变成 $(x, x, y - x)$，之后还可以变成 $(x, x \pm k, y - x \mp k)$ 之类的东西。显然的是后面两者不可能都为必败，如果都为必胜，那么一定存在一个状态同时属于两者的后继，也一定为当前状态的后继，是必败态。所以这个状态必胜。

然后考虑 $(0, 0, x)$ 和 $(0, x, x)$，两者是对称的，所以只需要考虑一种情况即可。

对于 $(0, 0, x)$，考虑到三个数不同时必胜，那么唯一可能的操作是：$\to (0, \lfloor \frac x2 \rfloor, \lceil \frac x2 \rceil)$，那么当 $x \equiv 1 \pmod 2$ 时，显然必败，当 $x \equiv 0 \pmod 2$ 时 $sig(0, 0, x) = !sig(0, \frac x2, \frac x2) = !sig(0, 0, \frac x2)$。这里不妨设 $sig(x, y, z) = [sg(x, y, z) > 0]$。

所以得出的结论是若将 $x$ 分解成 $a 2^k$ 的形式，那么只需要判断 $k$ 的奇偶性即可。

问题是转换依靠做差，现在考虑两数相减最低的那个 $1$ 在哪里？注意到放在从低到高的 01trie 上第一个分叉的位置就是相减后最低的 $1$ 的位置。于是直接 01trie 上和一和即可。复杂度 $O(n \log V)$。

https://codeforces.com/gym/104639/problem/F

path 路径

求出一条从 $a_1$ 到 $a_l$ 的路径 $b$，满足 $a$ 是 $b$ 的一个子序列且 $b$ 中不存在相邻三个元素 $x, y, z$ 满足 $x = z$ 的最短路。
此外，你需要支持对 $a$ 序列的 $q$ 次单点修改，每次修改后输出最短路。若不存在合法路径则输出 $-1$。

首先考虑怎么骗分。

1. 最短路，注意到这里需要与边相关的信息，那么将 $dis_{i, j}$ 定义为边 $i$ 到 $j$ 的最短路，于是类似的跑 djk 即可做到 $O(m^2 \log m)$。
2. 序列信息，考虑两个点，枚举入度和出度即可。

这样大概是 $O(m^2 l)$ 的，实际上跑不满。

前面一半复杂度是正确了，后面一部分呢？考虑可不可以减少状态数。

一个傻逼但是正确的想法是：

1. 优先选择最短路，然后选择稍劣的。
2. 这个劣的可能是一边不符合，也可能是两边不符合。

于是自然的有 $4$ 个状态，最短路，与最短路至多撞了一边，与最短路不撞边。

于是可以 $O(4^4 l)$，利用线段树优化到 $O(4^4 \log l)$。

但是发现合并的状态数玩意显然很不优秀，考虑定义 $M_{i, j}$ 表示由 $i$ 状态开始，能否转移到 $j$ 状态，如果可以，则为最短距离，否则为 inf，那么由于少了判断合法的要求，于是只需要 $O(4^3 \log l)$ 即可。