← 返回题目列表

AtCoder · kupc2024_i

I. 我讨厌异或和

中文机器翻译题面 查看原题

配点 : 100 点

問題文

正整数 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 ,由非负整数组成的长度 总和是 N 的序列 所有 S 的分数总和 除以 998244353 后求余数。

制約

  • 1\leq N\leq 10^{9}
  • 1\leq M\leq 10^{5}
  • 所有输入均为整数

部分点

这个问题有多个部分点。 如果正确答案是满足

  • N \leq 3000, M = 1 的数据集 如果满足 1 点。
  • N \leq 10^6, M = 1 的数据集的答案是正确的,则附加 跨 1 点。

入力

输入是按以下格式从标准输入给出的。

N\ M

出力

M 线输出。 当i\ (1\leq i\leq M) 在线 S=i 时打印答案。


入力例 1

4 1

出力例 1

18

例如 自从 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

202515 1

出力例 2

631322682

998244353 后的余数。


入力例 3

1000000000 20

出力例 3

450736580
222005843
791558300
565944390
287066035
818826101
538663305
222889651
450257059
718428507
230132846
653810630
380943894
21756026
863202268
823515972
834078326
615162787
221193562
85328814