Codeforces Round 955 (Div. 2, with prizes from NEAR!)

重生之我是 Jumping

比赛链接

Problems	AC
A. Soccer	○
B. Collatz Conjecture	○
C. Boring Day	○
D. Beauty of the mountains	○
E. Number of k-good subarrays	⊕
F. Sorting Problem Again	⊕

A

Code

B

Code

C DP

Code

D 裴蜀定理

地图是一张表格，包含 $n$ 行和 $m$ 列，每个单元格包含一个非负整数，代表山脉的高度。

他还注意到山脉有两种类型：

• 有雪山。
• 没有雪山。

Nikita 希望有雪山的山脉高度总和等于没有雪山的山脉高度总和。

Nikita 可以对大小为 $k \times k$ 的子矩阵执行如下变换：他可以将一个整数常数 $c$ 添加到此区域内的山脉高度，但山脉类型保持不变。Nikita 可以为每个变换独立选择常数 $c$ 。请注意， $c$ 可以为负数。

在进行变换之前，Nikita 会要求您找出是否有可能实现总和相等，或者是否不可能。即使山脉变成峡谷并且高度为负数，代价也无关紧要。

如果地图上仅显示一种类型的山脉，则另一种类型的山脉的高度总和将被视为零。

$1 \le n, m \le 500, 1 \le k \le min(n, m)$

对于每个子矩阵，其实收益相当于 这个子矩阵里面两种元素的个数差

那么问题转化为有大约 $n^2$ 个非负整数，每个可以任选无限多个，能否将最后的和凑成 $X$

裴蜀定理的多元推广，算 GCD 即可

Code

E 数位 DP

令 $bit(x)$ 表示非负整数 $x$ 的二进制表示中 1 的数量。

如果数组的子数组仅由二进制表示中 1 不超过 $k$ 个数字组成，则称该子数组为 $k$-good，即，如果对于任何 $i$ 都满足 $l \le i \le r$ 条件 $bit(a _ {i}) \le k$ ，则数组 $a$ 的子数组 $(l, r)$ 为 good。

给定一个长度为 $n$ 的数组 $a$ ，由从 $0$ 开始的连续非负整数组成，即，对于 $0 \le i \le n - 1$ (以 $0$ 为基础的索引)，其值为 $a _ {i} = i$ 。您需要计算此数组中 $k$-good 的数量。

由于答案可能非常大，请将其以 $10^{9} + 7$ 为模输出。

$1 \le n \le 10^{18}, 1 \le k \le 60$

参考自 cup-pyy

可以看出合法的区间是成段的

假设不存在 n 的限制，每个区间都可以被一组左闭右开的端点表示。假若右端点是 xxxx101111 有 k + 1 个 1，那么左端点就是 xxxx100000，因为再减 1 的话变成 xxxx011111，也会有 k + 1 个 1

所以只要 最后一个 0 的位置被确定了，那么最后一段 1 的数量也就确定了，区间的长度也就确定了。用数位 dp 的方式去搜索右端点来实现。

注意到还有 n 的限制，因为我们是搜索右端点的，所以有些左端点小于等于 n 右端点 大于 n 的区间被忽略了，我们最后需要补上这一部分区间。

Code

F

你有一个包含 $ n $ 个元素的数组 $ a $。该数组将进行 $ q $ 次修改。在每次修改之前和之后，你需要确定以下内容：

找到一个需要排序成非递减顺序的最短子数组，使整个数组 $ a $ 变为非递减顺序。

更具体地，你需要选择一个数组的子数组 $(l, r)$ ，使得 $ r - l + 1 $ 的值最小。然后，你会对子数组 $ a_{l}, a_{l + 1}, \ldots, a_{r} $ 进行排序，并希望满足条件 $ a_{i} \le a_{i + 1} $ 对于所有 $ 1 \le i < n $ 成立。如果数组已经是非递减顺序的，那么 $ l $ 和 $ r $ 应该被视为等于 $-1$。

注意，找到这样的 $(l, r)$ 并不会改变数组的任何元素。修改本身的形式为：对给定的位置 $ pos $ 和值 $ x $，进行赋值 $ a[pos] = x $。

Hint: 如果您维护一组这样的索引 $i$ : $a_{i} <a_{i - 1}$ ，那么这能有什么帮助吗？

这样维护后序列变成了形如 0001010111000 的样子。

注意到，从开头到第一个 1，和最后一个 1 到结尾这两个区间都是本身就有序的，中间一段不可名状物体。对于中间这一段是一定要全部排序的，那么序列变成了三段有序的（拼在一起不一定有序）。为了使得拼在一起有序，需要知道中间那一段的 min 和 max，然后在前面一段查 min 的位置，后面一段查 max 的位置

代码实现用 multiset + 二分 可以比较优雅。

Code