#P18755. [2027年国家集训队互测] Tomoshibi

    ID: 18091 传统题 3000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-普通生成函数卷积转化NTT递归拆解依赖阶乘逆元预处理

[2027年国家集训队互测] Tomoshibi

Tomoshibi

题目描述

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

用 ai(t)∈{0,1}a_i(t)\in\{0,1\} 表示第 ii 盏灯在第 tt 秒的状态,其中 11 表示亮,00 表示灭。第 00 秒的状态称为初始状态。

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

$$a_i(t+1)=a_i(t)\oplus a_{(i+1)\bmod N}(t),\qquad 0\le i<N.$$

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

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

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

  • 初始状态中恰好有 kk 盏灯亮。

  • 熄灭时刻恰好为 TT。

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

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

输入格式

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

输出格式

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

样例 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=2pN=2^p,其中 0≤p≤200\le p\le20;

  • 1≤T≤N1\le T\le N。

子任务 分值 额外限制
1 10 p≤4p\le4
2 p≤8p\le8
3 p≤10p\le10
4 20 p≤14p\le14
5 10 p≤16p\le16
6 p≤18p\le18
7 T=1T=1 或 T=NT=N
8 20 无额外限制

样例附件:下载。