AT_kupc2024_i I Hate Xor Sum

给定正整数 $N,M$。 对于由非负整数构成的长度为 $N$ 的数列 $A$，存在唯一的、满足下述条件的非负整数 $X_{i,j}\ (1\leq j\leq i\leq N)$： - $X_{i,1}=A_i\ (1\leq i\leq N)$ - $X_{i,j}=X_{i-1,j-1}\oplus X_{i,j-1}\ (2\leq j\leq i\leq N)$ 其中，$\oplus$ 表示按位异或运算。在这种情况下，$\sum_{i=1}^{N}\sum_{j=1}^{i}X_{i,j}$ 的值被称为数列 $A$ 的**分数**。 对于 $S=1,2,\dots,M$ 的每个 $S$，请你计算所有长度为 $N$、元素非负且元素和为 $S$ 的数列 $A$ 的分数的总和，并对结果取 $998244353$ 的余数。

输入以如下格式通过标准输入给出。 > $N\ M$

请输出 $M$ 行。第 $i\ (1\leq i\leq M)$ 行输出 $S=i$ 时的答案。

## 部分分数 本题设有多组部分分数。 - 当 $N \leq 3000, M = 1$ 的数据集全部答对时，获得 $1$ 分。 - 当 $N \leq 10^6, M = 1$ 的数据集全部答对时，额外获得 $1$ 分。 ## 样例解释 1 例如，当 $A=(0,1,0,0)$ 时，$X_{i,j}$ 计算如下，分数为 $5$。 - $X_{1,1}=0$ - $X_{2,1}=1,\ X_{2,2}=1$ - $X_{3,1}=0,\ X_{3,2}=1,\ X_{3,3}=0$ - $X_{4,1}=0,\ X_{4,2}=0,\ X_{4,3}=1,\ X_{4,4}=1$ ## 样例解释 2 请对 $998244353$ 取模输出。 ## 数据范围 - $1\leq N\leq 10^{9}$ - $1\leq M\leq 10^{5}$ - 所有输入均为整数。 由 ChatGPT 5 翻译