P14674 [ICPC 2025 Seoul R] Fair Problemset

本题采纳与 M 题 "Triple Fairness" 完全相同的 **公平试题集** 定义。 ICPC 是一项团队竞赛。每个团队有三名成员。在比赛开始时，大多数团队会将 $3n$ 道题平均分配。他们通常使用以下两种常见方法来分配题目： 1. **顺序分配**：每位成员从 $3n$ 道题中取一个连续的 $n$ 道题块。具体来说，第一名成员取题目 $1, \cdots, n$，第二名成员取题目 $n+1, \cdots, 2n$，第三名成员取题目 $2n+1, \cdots, 3n$。 2. **跳跃分配**：每位成员从 $3n$ 道题中取索引除以 $3$ 余数相同的题目。具体来说，第一名成员取题目 $1, 4, 7, \cdots, 3n-2$，第二名成员取题目 $2, 5, 8, \cdots, 3n-1$，第三名成员取题目 $3, 6, 9, \cdots, 3n$。 ICPC 首尔赛区科学委员会需要准备一个由 $3n$ 道题组成的试题集。每道题的难度用一个从 $1$ 到 $n$（含）的整数表示。对于每种难度，恰好有三道题具有该难度。因此，试题集中的难度排列可以看作一个长度为 $3n$ 的难度序列，其中包含每种 $n$ 个难度级别的三道题。 为了防止任何团队因选择的问题分配方法而获得优势或处于劣势，ICPC 首尔赛区科学委员会定义了一个称为 **公平试题集** 的标准。一个长度为 $3n$ 的难度序列被称为公平试题集，当且仅当它同时满足以下两个条件： 1. **顺序分配公平性**：当使用顺序分配时，对于每个难度级别 $i$ ($1 \le i \le n$)，三名成员每人恰好收到一道难度为 $i$ 的题。 2. **跳跃分配公平性**：当使用跳跃分配时，对于每个难度级别 $i$ ($1 \le i \le n$)，三名成员每人恰好收到一道难度为 $i$ 的题。 换句话说，无论选择两种方法中的哪一种，每个团队成员都必须被分配到恰好一道难度为 $1$ 到 $n$（含）中每个级别的题目。 给定一个正整数 $k$，请编写一个程序，对每个 $n = 1, 2, \cdots, k$，找出长度为 $3n$ 的公平试题集序列的数量。

你的程序需要从标准输入读取数据。输入恰好包含一行。该行包含两个整数 $k$ 和 $m$ ($1 \le k \le 10^6$； $10^8 < m < 10^9$； $m$ 是一个质数)。

你的程序需要向标准输出写入数据。你应该恰好输出 $k$ 行。在第 $n$ 行 ($1 \le n \le k$) 上，输出长度为 $3n$ 的公平试题集序列的数量，结果对 $m$ 取模。

以下是长度为 $9$ ($= 3 \times 3$) 的 $12$ 个公平试题集序列： ``` i. 1 2 3 2 3 1 3 1 2 ii. 1 2 3 3 1 2 2 3 1 iii. 1 3 2 2 1 3 3 2 1 iv. 1 3 2 3 2 1 2 1 3 v. 2 1 3 1 3 2 3 2 1 vi. 2 1 3 3 2 1 1 3 2 vii. 2 3 1 1 2 3 3 1 2 viii. 2 3 1 3 1 2 1 2 3 ix. 3 1 2 1 2 3 2 3 1 x. 3 1 2 2 3 1 1 2 3 xi. 3 2 1 1 3 2 2 1 3 xii. 3 2 1 2 1 3 1 3 2 ``` 翻译由 DeepSeek V3 完成