#1990. Tomoshibi

    ID: 1990 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4599来源:qoj.ac数据:公开样例组合数学

Tomoshibi

Tomoshibi

题目描述

标题: Tomoshibi - Problem - QOJ.ac

#21429. Tomoshibi

Statistics

题目描述

有 N 盏灯排成一个环,依次编号为 0,1,…,N−1。保证 N 是 2 的非负整数次幂。

用 ai(t)∈{0,1} 表示第 i 盏灯在第 t 秒的状态,其中 1 表示亮,0 表示灭。第 0 秒的状态称为初始状态。

每经过一秒,所有灯同时按照下面的规则改变状态:

ai(t+1)=ai(t)⊕a(i+1)modN(t),0≤i<N.

其中 ⊕ 表示按位异或。更新使用的两个状态都来自第 t 秒。

一个初始状态的熄灭时刻定义为所有灯第一次同时熄灭的时刻。如果初始状态中所有灯都已经熄灭,则其熄灭时刻为 0。

给定整数 T,请对每个 k=0,1,…,N,计算满足以下两个条件的初始状态数量:

  1. 初始状态中恰好有 k 盏灯亮。
  2. 熄灭时刻恰好为 T。

答案可能很大,请将每个答案对 998244353 取模。

只要某个编号的灯的初始状态不同,就视为不同的初始状态,即便两个状态可以通过旋转变成相同的状态,他们依然被算作不同的状态。

输入格式

输入一行,包含两个整数 N,T。

输出格式

输出一行,包含 N+1 个整数,从小到大依次为 k=0,1,…,N 的答案,每个答案对 998244353 取模。相邻整数之间用一个空格隔开。

样例 1

输入

4 3

输出

0 0 4 0 0

样例 2

输入

8 5

输出

0 0 0 0 16 0 0 0 0

样例 3

输入

4 4

输出

0 4 0 4 0

数据范围

对于所有测试数据:

  • N=2p,其中 0≤p≤20;
  • 1≤T≤N。

子任务 分值 额外限制 1 10 p≤4 2 10 p≤8 3 10 p≤10 4 20 p≤14 5 10 p≤16 6 10 p≤18 7 10 T=1 或 T=N 8 20 无额外限制

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 3
0 0 4 0 0

样例 2

8 5
0 0 0 0 16 0 0 0 0