AT_arc204_d [ARC204D] Favorite Interval
题目描述
给定整数 $N, L, R$。
这些整数满足以下条件:
- $2 \leq N$
- $0 \leq L < R \leq N$
- $(L, R) \neq (0, N)$
初始化一个长度为 $N$ 的序列 $A = (A_{0}, A_{1}, \dots , A_{N - 1})$,其中 $A = (0, 1, \dots, N - 1)$。
选择一个排列 $P = (P_{0}, P_{1}, \dots, P_{N - (R - L) - 1})$,该排列是 $(R - L, R - L + 1, \dots, N - 1)$ 的一个全排列,并按顺序对 $i = 0, 1, \dots, N - (R - L) - 1$ 执行以下操作:
- 令 $a$ 为 $P_{i}$ 除以 $|A|$ 的余数,移除 $A_{a}$(每次移除元素后,序列 $A$ 的下标会重新从 $0$ 编号)。
判断是否存在某个 $P$,使得最终 $A = (L, L + 1, \dots, R - 1)$,如果存在,输出其中一个 $P$。
输入格式
输入从标准输入读入,格式如下:
> $N$ $L$ $R$
输出格式
如果不存在使 $A = (L, L + 1, \dots, R - 1)$ 的 $P$,输出 `No`。
如果存在,输出一种方案,格式如下:
> Yes $P_{0}$ $P_{1}$ $\cdots$ $P_{N - (R - L) - 1}$
具体来说,第一行输出 `Yes`,第二行输出 $P_{0}, P_{1}, \dots, P_{N - (R - L) - 1}$,用空格分隔。
如果有多种方案,输出任意一种均可。
说明/提示
### 样例解释 1
当选择 $P = (2, 4, 5, 3)$ 时,对 $A = (0, 1, 2, 3, 4, 5)$ 进行四次操作如下:
- $P_{0} = 2$,$|A| = 6$,余数为 $2$,移除 $A_{2} = 2$,此时 $A = (0, 1, 3, 4, 5)$。
- $P_{1} = 4$,$|A| = 5$,余数为 $4$,移除 $A_{4} = 5$,此时 $A = (0, 1, 3, 4)$。
- $P_{2} = 5$,$|A| = 4$,余数为 $1$,移除 $A_{1} = 1$,此时 $A = (0, 3, 4)$。
- $P_{3} = 3$,$|A| = 3$,余数为 $0$,移除 $A_{0} = 0$,此时 $A = (3, 4)$。
因此,选择 $P = (2, 4, 5, 3)$ 可以达成目标。输出 $P = (5, 2, 4, 3)$ 也是可以的。
### 数据范围
- $2 \leq N \leq 2 \times 10^{5}$
- $0 \leq L < R \leq N$
- $(L, R) \neq (0, N)$
- 所有输入均为整数。
由 ChatGPT 4.1 翻译