P2931 [USACO09HOL] Pearl Bracelet G【征集 SPJ】

Bessie 收到了一个魔法手镯，这是一套稀有的黑珍珠，是她最喜欢的节日礼物。Bessie 非常喜欢这个手镯，并惊奇地发现每颗珍珠上都刻有一个小数字。她注意到，如果通过围绕某个点弯曲手镯来排列珍珠的所有可能方式（见下文），手镯上下两侧对应数字的珍珠的「渐进」和在模 $M$（$2 \leq M \leq 100$）比较时从未匹配过。「渐进」和的例子如下。 假设模 $M$ 为 $3$。考虑一个有 $N=6$ 颗珍珠的手镯，珍珠上依次刻有数字 $0, 1, 0, 2, 1, 0$。我们将这个手镯用它的扣子这样表示： >0-1-0-2-1-0 这个六颗珍珠的手镯可以在地上以五种不同的方式排列，使得某些珍珠「对应」彼此（见下文）。我们可以对上面对应的珍珠进行「渐进」和模 $M$ 运算，也可以对下面对应的珍珠进行和模 $M$ 运算，如同用 ONE-sums, TWO-sums, THREE-sums（当 $N > 6$ 时以此类推）所示。 ``` | THREE-sums | TWO-sums | ONE-sums --------------+------------------------+-------------------+--------- >0-1-0-2-1 | | | => 1 | | | | >0 | | | => 0 --------------+------------------------+-------------------+--------- >0-1-0-2 | | => 0+2 = 2 | => 2 | | | | >0-1 | | => 0+1 = 1 | => 1 --------------+------------------------+-------------------+--------- >0-1-0 | => 0+1+0 = 1 | => 1+0 = 1 | => 0 | | | | >0-1-2 | => 0+1+2 = 3 mod 3 = 0 | => 1+2 mod 3 = 0 | => 2 --------------+------------------------+-------------------+--------- >0-1 | | => 0+1 = 1 | => 1 | | | | >0-1-2-0 | | => 2+0 = 2 | => 0 --------------+------------------------+-------------------+--------- >0 | | | => 0 | | | | >0-1-2-0-1 | | | => 1 ``` Bessie 注意到所有的和对都包含不同的数字，并且听说对于所有的魔法手镯都是如此。Bessie 想知道具有这种唯一和性质的最长可能手镯是多少。 给定 $M$，找到一组非常长（但不超过 $20000$）的数字，可以刻在黑珍珠上以保持手镯的这种唯一和性质。 这是一个仅输出题目，$15$ 个输入文件可以从以下地址下载：http://ace.delos.com/perlbrac.zip 评分：此问题的评分将是相对的；每个测试用例的整数得分（满分 $10$ 分）将是 $[10 * \sqrt{Y \div B})]$，其中 $Y$ 是你的解的长度，$B$ 是所有参赛者中最佳解的长度，$[]$ 为取整函数。 反馈：当你提交一个文件进行评分时，它将被检查格式和有效性（即是否满足所需的数值属性），并且你将被告知结果。

- 第 $1$ 行：两个用空格分隔的整数：案例编号和 $M$。

- 第 $1$ 行：包含任务名称和案例编号的单行：#FILE perlbrac CASENUM。 - 第 2 行：单行包含一个整数 $N$（必须不大于 $20000$）。 - 第 $3$ 到 $N+1$ 行：第 $i+2$ 行包含一个整数，即刻在手镯上第 $i$ 颗珍珠上的整数；这个数字应在 $0$ 到 $M - 1$ 之间（含）。

（由 ChatGPT 4o 翻译，@simple_child 修缮）