AT_pakencamp_2022_day3_h Exactly K Square Numbers

**由于发现了标准解答的错误，已用正确的解法进行了替换，并更改了题目的限制条件。（$M \leq 10^{12}$ 改为 $M \leq 10^9$）。对受影响的各位表示歉意。（15:29）** 给定正整数 $N, M$。 对于所有满足 $0 \leq K \leq N-1$ 的 $K$，请求出如下值对 $998244353$ 的余数： - 长度为 $N$ 的数列 $A = (A_1, A_2, \ldots, A_N)$，其中 $A_i$ 均为 $1$ 至 $M$ 之间的整数，且恰好存在 $K$ 个 $i\,(1\leq i\leq N-1)$ 使得 $A_i \times A_{i+1}$ 为完全平方数的数列 $A$ 的总数。

输入按以下格式从标准输入给出。 > $N$ $M$

请输出 $N$ 行。在第 $i\,(1\leq i\leq N)$ 行输出当 $K=i-1$ 时的答案。

### 样例解释 1 - 当 $K=0$ 时，满足条件的 $A$ 有 $(1,2,1),\ (2,1,2)$ 共 $2$ 种。 - 当 $K=1$ 时，满足条件的 $A$ 有 $(1,1,2),\ (1,2,2),\ (2,1,1),\ (2,2,1)$ 共 $4$ 种。 - 当 $K=2$ 时，满足条件的 $A$ 有 $(1,1,1),\ (2,2,2)$ 共 $2$ 种。 ### 数据范围 - $2 \leq N \leq 2000$ - $1 \leq M \leq 10^9$ - 输入均为整数。 由 ChatGPT 5 翻译