# 随机分析：概率

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

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

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

(本故事由GPT-6重写)

## 形式化问题描述

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

```text
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

### 输入

```text
1
1
```

### 输出

```text
1
```

### 样例 2

### 输入

```text
3
1 2 3
```

### 输出

```text
332748118 813384288 850356301
332748118 850356301 813384288
332748118 332748118 332748118
```

### 样例 3

### 输入

```text
3
1 1 3
```

### 输出

```text
147888053 0 850356301
184860066 0 813384288
665496236 0 332748118
```

## 样例解释

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

![三个位置和三个数值的最终概率](assets/probabilities.svg)

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

## 数据范围与保证

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

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

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