问题#

对于长度为偶数的排列 $^{\text{∗}}$ 来说长度为偶数的 $p$ ，可以进行以下运算：

• 初始化计数器 $c = 0.$
• 对于从 $1$ 到 $n,$ 的每个 $i$ ，要么在 $c$ 中加上 $i \cdot p_i$ ，要么从 $c$ 中减去 $i \cdot p_i$ ，要么什么都不做。

让计数器的最终值为 $c_{\mathrm{final}}.$

形式上，对于每个 $i \in \{1,\ldots,n\},$ 考虑集合 $S_i = \{-i \cdot p_i, 0, i \cdot p_i\}$ 并选择一些 $x_i \in S_i.$ 集合 $c_{\mathrm{final}} = \sum_{i = 1}^{n}x_i.$

给你一个偶整数 $n$ 。请找出长度为 $n$ 的任意排列，使得无论选择何种运算，最终值 $c_{\mathrm{final}}$ 都不会是 $1.$ 。

$^{\text{∗}}$ 长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（ $2$ 在数组中出现了两次）， $[1,3,4]$ 也不是一个排列（ $n=3$ ，但数组中有 $4$ ）。

构造#

如果所有 i * p[i] 都是偶数，那么无论怎么组合，结果永远是偶数，不可能等于 1

让所有 i * p[i] 都是偶数。这样最终和只能是偶数，永远不等于 1。

即：

• 当 i 为奇数时，p[i] 必须是偶数
• 当 i 为偶数时，p[i] 可以是任意值（因为 i 已经是偶数）

1
for _ in range(int(input())):
2
    n = int(input())
3
    odd = []
4
    even = []
5
    for i in range(1, n + 1):
6
        if i % 2 == 1:
7
            odd.append(i)
8
        else:
9
            even.append(i)
10
    ans = [0] * n
11
    for i in range(n):
12
        if (i + 1) % 2 == 1:
13
            ans[i] = even.pop()
14
        else:
15
            ans[i] = odd.pop()
16
    print(*ans)

问题#

给你一个整数 $n.$ 构造一个由 $n$ 个不同的正整数 $a_1, \ldots, a_n$ 组成的数组，使得对于所有的 $i \, (1 \le i \le n)$ , $a_1 + a_2 + a_3 + \ldots + a_n$ 都能被 $a_i,$ 整除，或者确定不存在这样的数组。

构造#

当 n = 1 时，任何数都满足（比如 1）。

当 n = 2 时，设两个数为 a, b (a ≠ b)。若 S = a + b 能被 a 和 b 整除，则 a | b 且 b | a，故 a = b，矛盾。因此 n = 2 无解。

当 n ≥ 3 时，

1. 从 [1, 2, 3] 开始，总和 S = 6。三个数都是 6 的约数。

2. 每次增加一个新数，令新数为当前总和 S 本身（即前一个数的两倍，如果从 3 之后都是 2 倍关系）。

   • 例如 n=4：在 [1,2,3] 后加上 6，新总和 = 12，新数组 [1,2,3,6]。12 能被所有数整除。
   • n=5：加上 12，总和 = 24，数组 [1,2,3,6,12]。

3. 一般地，数组为：1, 2, 3, 6, 12, 24, …, 3×2^{n-3}。

   总和 S = 3×2^{n-2}，每个元素都是 S 的约数（1, 2, 3 整除 S，后面的都是 3 乘以 2 的幂，自然也整除 S）。

1
for _ in range(int(input())):
2
    n = int(input())
3
    if n == 1:
4
        print(1)
5
    elif n == 2:
6
        print(-1)
7
    else:
8
        ans = [1, 2, 3]
9
        cur = 3
10
        for i in range(4, n + 1):
11
            cur *= 2
12
            ans.append(cur)
13
        print(*ans)

问题#

定义长度为 $k$ 的数组 $b$ 的交替和为 $\sum_{i = 1}^{k}(-1)^{i+1}b_i$ 。

给你一个长度为 $n$ 的非递减数组 $a$ $^{\text{∗}}$ ，对于所有的 $1 \le i \le n,$ ，要么 $a_i = -1$ 要么 $a_i$ 是正整数。求使得序列 $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ 的交替和为 $0.$ 的序列 $1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$ 的个数。因为这个数可能很大，所以输出它的模数 $10^9+7$ 。

如果 $k_1 \neq k_2$ 或存在 $j$ 使得 $i_j \neq i'_j.$ 的两个索引集 $i_1, \ldots, i_{k_1}$ 和 $i'_1, \ldots, i'_{k_2}$ 被认为是不同的，那么 $k_1 \neq k_2$ 和 $i'_1, \ldots, i'_{k_2}$ 就被认为是不同的。

$^{\text{∗}}$ 如果有 $a_1 \le a_2 \le \ldots \le a_n$ 个序列 $a_1, \ldots, a_n$ 是非递减序列。

数学#

交替和为 0 需要满足：

• 子序列长度必须为偶数（奇数长度交替和必为正）
• 每对 (b1-b2), (b3-b4), ... 都必须为 0
• 所以相同值必须出现偶数次

对于每个值有 cnt 个元素，选偶数个的方案数 = 2^(cnt-1)

总方案数 = ∏ 2^(cnt_i - 1) = 2^(n - d)，其中 d = 不同值的个数。

2. 包含 -1 的情况#

-1 可以充当任意值来”平衡”交替和。

情况 A：选偶数个 -1

• -1 之间互相抵消，等价于正整数的情况
• 方案数 = 2^(n - d - 1)（扣掉 -1 那一组的影响）

情况 B：选奇数个 -1

• 奇数个 -1 导致需要正整数部分凑出 -1（或 +1 取决于位置）
• 必要条件：存在相邻值 (v, v+1) 都出现在数组中
• 选奇数个 -1 的方案数 = 2^(c-1)（c 是 -1 的个数）
• 对于存在 (v, v+1) 的对数 P，方案数为 2^(n - d - c) × P

3. 最终公式#

设：

• c = -1 的个数
• N = 正整数个数 = n - c
• d = 不同正整数值的个数
• P = 满足 v 和 v+1 都存在的对数

答案：

• 无 -1：2^(N - d)

• 有 -1：2^(n - d - 1) + 2^(c-1) × 2^(N - d) × P

  = 2^(n - d - 1) × (1 + P)

因为 c + N - d = n - d，提取公因式后得 2^(n-d-1) × (1 + P)。