题目详情题解（0）讨论（0）提交记录（0）

AT_kupc2024_i.I Hate Xor Sum

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定正整数 N,MN,M。

对于由非负整数构成的长度为 NN 的数列 AA，存在唯一的、满足下述条件的非负整数 Xi,j (1≤j≤i≤N)X_{i,j}\ (1\leq j\leq i\leq N)：

  • Xi,1=Ai (1≤i≤N)X_{i,1}=A_i\ (1\leq i\leq N)
  • Xi,j=Xi−1,j−1⊕Xi,j−1 (2≤j≤i≤N)X_{i,j}=X_{i-1,j-1}\oplus X_{i,j-1}\ (2\leq j\leq i\leq N)

其中，⊕\oplus 表示按位异或运算。在这种情况下，∑i=1N∑j=1iXi,j\sum_{i=1}^{N}\sum_{j=1}^{i}X_{i,j} 的值被称为数列 AA 的分数。

对于 S=1,2,…,MS=1,2,\dots,M 的每个 SS，请你计算所有长度为 NN、元素非负且元素和为 SS 的数列 AA 的分数的总和，并对结果取 998244353998244353 的余数。

输入格式

输入以如下格式通过标准输入给出。

N MN\ M

输出格式

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

输入输出样例

  • 输入#1

    4 1

    输出#1

    18

  • 输入#2

    202515 1

    输出#2

    631322682

  • 输入#3

    1000000000 20

    输出#3

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

说明/提示

部分分数

本题设有多组部分分数。

  • 当 N≤3000,M=1N \leq 3000, M = 1 的数据集全部答对时，获得 11 分。
  • 当 N≤106,M=1N \leq 10^6, M = 1 的数据集全部答对时，额外获得 11 分。

样例解释 1

例如，当 A=(0,1,0,0)A=(0,1,0,0) 时，Xi,jX_{i,j} 计算如下，分数为 55。

  • X1,1=0X_{1,1}=0
  • X2,1=1, X2,2=1X_{2,1}=1,\ X_{2,2}=1
  • X3,1=0, X3,2=1, X3,3=0X_{3,1}=0,\ X_{3,2}=1,\ X_{3,3}=0
  • X4,1=0, X4,2=0, X4,3=1, X4,4=1X_{4,1}=0,\ X_{4,2}=0,\ X_{4,3}=1,\ X_{4,4}=1

样例解释 2

请对 998244353998244353 取模输出。

数据范围

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

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页