署前街少年 - 奇变偶不变，符号看象限：数列变换算法详解

题目背景

时光无法缝补那块破碎的黑板
虚荣的少年与署前街越来越远
——赵雷，《署前街少年》

题目描述

某 E 得到了一个长度为 $2N$ 的数列 $a_1, a_2, a_3, \dots a_{2N}$，数列的第 $i$ 个数为 $a_i$。

奇变偶不变，符号看象限。这是三角函数诱导公式的重要口诀。某 E 同样想对数列实施这样的变换，具体来说：

对于 $a_i$，若 $i \bmod 2=0$，则称 $a_i$ 为偶位数；若 $i \bmod 2 = 1$，则称 $a_i$ 为奇位数。
对于 $a_i$，记 $i \bmod k = p$，则称 $a_i$ 为第 $p$ 象限数，其中 $k$ 为给定的参数。

奇变偶不变，符号看象限。某 E 将遵循以下的规则对数列进行变换：

若 $a_i$ 为偶位数，则 $a_i$ 不变。
若 $a_i$ 为奇位数，设 $a_i$ 为第 $p$ 象限数，则 $a_i$ 变为所有第 $p$ 象限数的和对 $i$ 取模的值。

某 E 想知道，变换后的数列是什么样的。

输入格式

输入共两行。

输入的第一行为两个整数 $N,k$。

输入的第二行为 $2N$ 个整数，第 $i$ 个代表 $a_i$。

输出格式

输出一行 $2N$ 个整数，第 $i$ 个代表变换后的 $a_i$。

样例 #1

样例输入 #1

10 4
5 2 0 4 7 6 2 7 1 3 5 7 9 45 3 6 12 36 78 1

样例输出 #1

0 2 1 4 4 6 4 7 7 3 0 7 8 45 13 6 0 36 12 1

提示

对于 $40%$ 的测试数据，$1 \le N \le 1000$，$2 \le k \le 10$。
对于 $100%$ 的测试数据，$1 \le N \le 5 \times 10^5$，$2 \le k \le 10^4$，$0 \le a_i \le 10^6$ 。cpp code内容：### 解题思路

根据题目要求，我们需要对输入的数列进行变换。首先，我们可以使用两个数组 a 和 b 分别保存原始数列和变换后的数列。然后，我们遍历原始数列，根据当前元素的奇偶性和所在的象限，更新变换后的数列。

具体的实现步骤如下：

读取输入的 $N$ 和 $k$。
读取输入的数列，并将数列保存到数组 a 中。
初始化数组 b，将数组中的所有元素初始化为 0。
遍历数组 a，对于每个元素 $a_i$，执行以下操作：
- 如果 $i$ 是偶位数，则将 $a_i$ 添加到数组 b 的相应位置上。
- 如果 $i$ 是奇位数，则计算第 $p$ 象限的和，并将结果对 $i$ 取模，然后将结果添加到数组 b 的相应位置上。
将数组 b 输出。

复杂度分析

由于需要遍历整个数列，并对每个元素进行计算，所以时间复杂度为 $O(N)$。同时，使用了两个数组来保存数列，所以空间复杂度为 $O(N)$。

代码实现

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, k;
    cin >> N >> k;

    vector<int> a(2*N);
    for (int i = 0; i < 2*N; i++) {
        cin >> a[i];
    }

    vector<int> b(2*N, 0);
    for (int i = 0; i < 2*N; i++) {
        if (i % 2 == 0) {
            b[i] = a[i];
        } else {
            int p = i % k;
            for (int j = 0; j < 2*N; j += 2) {
                b[i] += a[(j + p) % (2*N)];
            }
            b[i] %= (2*N);
        }
    }

    for (int i = 0; i < 2*N; i++) {
        cout << b[i] << ' ';
    }
    cout << endl;

    return 0;
}