随机分析：概率¶

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

实验室用一段固定顺序的随机交换程序打乱编号卡片。研究员想分析每个位置最终的数值分布。

(本故事由GPT-6重写)

给定长度为 \(n\) 的整数序列 \(a_1,\ldots,a_n\) ，下标从 \(1\) 开始。元素允许重复。对当前序列执行：

for i = 1, 2, ..., n:
    r = uniformly_random_integer(1, n)
    swap(a[i], a[r])

每轮的随机数独立产生，等概率取 \(1\) 到 \(n\) 中的任意整数，包含当前下标 \(i\) .交换会立即改变后续轮次使用的序列。设最终序列为 \(A_1,\ldots,A_n\) .

求完整概率矩阵 \(P_{i,j}=\Pr(A_i=j)\) ，其中行表示位置，列表示数值，\(1\le i,j\le n\) .相同数值的不同元素共同计入对应列；未出现的数值对应零概率列。

结果按模 \(M=998244353\) 表示：若一个结果为非负有理数 \(p/q\) ，其中 \(q>0\) ，输出 \(p\cdot q^{-1}\bmod M\) 在 \([0,M-1]\) 内的代表元。零结果输出 \(0\) .本题范围保证所需分母在模 \(M\) 意义下可逆。

第一行一个整数 \(n\) .第二行 \(n\) 个整数 \(a_1,\ldots,a_n\) .

输出 \(n\) 行，每行 \(n\) 个整数。第 \(i\) 行第 \(j\) 个表示 \(P_{i,j}\) 的模意义结果。

1
1

3
1 2 3

332748118 813384288 850356301
332748118 850356301 813384288
332748118 332748118 332748118

3
1 1 3

147888053 0 850356301
184860066 0 813384288
665496236 0 332748118

第二组共有 \(3^3=27\) 个等概率的随机选择序列。将每种最终状态计数，可以得到如下分子矩阵，所有格子的分母均为 \(27\) .第三组中，值为 \(1\) 的两个元素都计入第一列，第二列全部为零。

三个位置和三个数值的最终概率

行表示最终位置，列表示数值。表中计数除以 \(27\) 即为对应概率。

所有数据满足：\(1\le n\le300\) ，\(1\le a_i\le n\) .

本题的规模规格由 Codex（GPT-6）制定为 \(n\le300\) ；元素范围保持为 \(1\le a_i\le n\) .

分值比例	额外条件
100%	无额外条件