P8880 无知时诋毁原神 题解

玄学OIER荷蒻 · 2022-12-04 22:27:47 · 题解

很明显，这是一个构造题。

我们先来讨论 n \mod 2=0 的情况

情况1：无解

三个数列的和都是 \sum_{i=0}^{n-1} \mod n。

套用等差数列求和公式，变成 \frac{n\times(n-1)}{2} \mod n。

再化简，得到 \frac{n}{2} \mod n。

两个构造序列的总和之和应该等于已知的数列，在模数为 n 的意义下。 把它们两个相加，一定会得到 0。

而 0 肯定不等于 \frac{n}{2} \mod n。

综上所述，在 n \mod 2=0 的情况下，无解。

情况2：构造解

对于 n \mod 2=1 接下来，我来说说我自己的构造。

对于和为 c,总数字个数为 n，构造两个数字。

将 n-g-1 放入数组一号。

将 2 \times g+1 \mod n 放入数组二号。

可以保证它们不冲突。

代码不贴了。