标签 数学归纳法 下的文章

「Codeforces 1186E」Vus the Cossack and a Field

题目链接：Codeforces 1186E

Vus 有一个 $n \times m$ 的 $01$ 矩阵，他通过如下方法构造了一个无限大的矩阵：

1. 计算出当前矩阵的反矩阵。即 $0$ 变成 $1$，$1$ 变成 $0$。
2. 将当前矩阵放在左上角和右下角，将反矩阵放在左下角和右上角。
3. 将得到的矩阵作为当前矩阵，回到步骤 $1$ 并不断重复。

我们将列从上到下标号为 $1$ 到 $\infty$，将行从左到右标号为 $1$ 到 $\infty$。接下来进行 $q$ 次询问，每次询问子矩阵 $(x_1, y_1, x_2, y_2)$ 的元素之和。

数据范围：$1 \le n, m \le 1000$，$1 \le q \le 10 ^ 5$，$1 \le x_1 \le x_2 \le 10 ^ 9$，$1 \le y_1 \le y_2 \le 10 ^ 9$。

「Codeforces 1148F」Foo Fighters

题目链接：Codeforces 1148F

你有 $n$ 个物品，每个物品有两个属性 $val_i$ 和 $mask_i$。保证最初 $val_i$ 的和非零。

你想要选择一个正整数 $s$ 并将所有物品的 $val_i$ 进行修改，第 $i$ 个物品的 $val_i$ 通过如下方法修改：

• 将 $mask_i$ 和 $s$ 在二进制下考虑。
• 计算 $s\ \text{AND}\ mask_i$ 的值。
• 如果 $s\ \text{AND}\ mask_i$ 的值中有奇数个 $1$，那么将 $val_i$ 替换为 $-val_i$；否则不进行修改。

你需要找到这样一个整数 $s$，使得所有物品 $val_i$ 的和相对最初的和正负号相反（不允许为 $0$）。但是和的绝对值可以是任意的。

数据范围：$1 \le n \le 3 \times 10 ^ 5$，$-10 ^ 9 \le val_i \le 10 ^ 9$，$1 \le mask_i, s < 2 ^ {62}$。

「ARC 103B」Robots Arms

题目链接：ARC 103B

Snuke 正在向他的工厂介绍一款机械臂：

• 机械臂由 $m$ 个部分和 $m + 1$ 个关节组成，关节标号为 $0$ 到 $m$。第 $i$ 个部分连着第 $i - 1$ 和 $i$ 个关节。第 $i$ 个部分的长度为 $d_i$。

• 对于每个部分，可以单独指定其动作。现在有 $4$ 种模式：$\text{L}$、$\text{R}$、$\text{D}$ 和 $\text{U}$。如果我么把工厂视为坐标平面，那么关节 $i$ 的位置将通过如下方法确定（我么将它的坐标表示为 $(x_i, y_i)$）：

  • $(x_0, y_0) = (0, 0)$。
  • 如果第 $i$ 个模式为 $\text{L}$，那么 $(x_i, y_i) = (x_{i - 1} - d_i, y_{i - 1})$。
  • 如果第 $i$ 个模式为 $\text{R}$，那么 $(x_i, y_i) = (x_{i - 1} + d_i, y_{i - 1})$。
  • 如果第 $i$ 个模式为 $\text{D}$，那么 $(x_i, y_i) = (x_{i - 1}, y_{i - 1} - d_i)$。
  • 如果第 $i$ 个模式为 $\text{U}$，那么 $(x_i, y_i) = (x_{i - 1}, y_{i - 1} + d_i)$。

Snuke 想要引入一种机械臂，以便通过正确的指定模式，使得关节 $m$ 可以到达所有的 $n$ 个点 $(X_1, Y_1), (X_2, Y_2),\cdots, (X_n, Y_n)$。请判断这是否可行。如果可行，那么请你构造一个满足条件的机械臂，并分别给出到达 $n​$ 个点的模式方案。

在你构造出的方案中，必须满足 $1 \le m \le 40$，$1 \le d_i \le 10 ^ {12}​$。

数据范围：$1 \le n \le 1000$，$-10 ^ 9 \le X_i, Y_i \le 10 ^ 9$。