Codeforces Round 869 (Div. 2) B. Indivisible

zsxuan / 2023-09-05 / 原文

给一个正整数 $n$ ，问能否构造出任意一个一个长为 $n$ 的排列满足 $\forall l,r,\ 1 \leq l < r \leq n,\ s.t.\ (r - l + 1) \nmid \sum_{i = l}^{r}a_i$ 。若能，输出这个排列。

典一：有关排列区间和的问题。

当排列长为 $n$ ，$length \leq n - 1$ 时排列位置构造的方式有很多，而 $length = n$ 时排列子段和严格为 $\sum_{i = 1}^{n} i = \frac{n(n+1)}{2}$
若有 $k \mid \frac{n(n+1)}{2}$ 容易发现提掉 $n$ 或 $n+1$ 后，剩下的一个数会因为奇偶性的不同导致是否合法。

显然 $\frac{n(n+1)}{2}$ 提掉区间长度 $(n - 1 + 1)$ 的倍数后余下 $\frac{n+1}{2}$ 。若 $n$ 为奇数则 $2 \mid n + 1$ ，不符合题目要求。

典二：整除与多项式相关问题。

如 $k \nmid f(i)$ ，构造方式为如何使 $f(i) \not \equiv 0 (\mod k)$ 。即 $f(i)$ 提掉 $k$ 的倍数后，余下部分非整数。

典三：排列 $a_i = i + (-1)^{i} = 2, 1, 4, 3, 6, 5, 8, 7, \cdots$ 的性质。

$S_{l, r} = \sum_{i = l}^{r} (i + (-1)^i) = \frac{(r - l + 1)(l + r)}{2} + \sum_{i = l}^{r}(-1)^i$
当 $r - l \equiv 1 (\mod 2)$ ，$S_{l, r} = \frac{(r - l + 1)(l + r)}{2}$ 。提掉 $(r - l + 1)$ 后，$2 \nmid l + r$ 。
当 $r - l \equiv 0 (\mod 2)$ ，$S_{l, r} = \frac{(r - l + 1)(l + r)}{2} + (-1)^l$ 。提掉 $(r - l + 1)$ 后，$1 \nmid \frac{(-1)^l}{r + l - 1}$ 。

此题当区间大小为 $1$ 时，不存在一组 $l, r$ ，默认合法。

view

#include <bits/stdc++.h>
void solve() {
	int n;std::cin >> n;
	if (n == 1) std::cout << 1 << '\n';
	else if (n & 1) std::cout << -1 << '\n';
	else {
		for (int i = 1, sgn = 1; i <= n; i++, sgn *= -1) {
			std::cout << (i + sgn) << " \n"[i == n];
		}
	}
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}