#P18755. [2027年国家集训队互测] Tomoshibi
[2027年国家集训队互测] Tomoshibi
Tomoshibi
题目描述
有 盏灯排成一个环,依次编号为 。保证 是 的非负整数次幂。
用 表示第 盏灯在第 秒的状态,其中 表示亮, 表示灭。第 秒的状态称为初始状态。
每经过一秒,所有灯同时按照下面的规则改变状态:
$$a_i(t+1)=a_i(t)\oplus a_{(i+1)\bmod N}(t),\qquad 0\le i<N.$$其中 表示按位异或。更新使用的两个状态都来自第 秒。
一个初始状态的熄灭时刻定义为所有灯第一次同时熄灭的时刻。如果初始状态中所有灯都已经熄灭,则其熄灭时刻为 。
给定整数 ,请对每个 ,计算满足以下两个条件的初始状态数量:
-
初始状态中恰好有 盏灯亮。
-
熄灭时刻恰好为 。
答案可能很大,请将每个答案对 取模。
只要某个编号的灯的初始状态不同,就视为不同的初始状态,即便两个状态可以通过旋转变成相同的状态,他们依然被算作不同的状态。
输入格式
输入一行,包含两个整数 。
输出格式
输出一行,包含 个整数,从小到大依次为 的答案,每个答案对 取模。相邻整数之间用一个空格隔开。
样例 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
数据范围
对于所有测试数据:
-
,其中 ;
-
。
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 10 | |
| 2 | ||
| 3 | ||
| 4 | 20 | |
| 5 | 10 | |
| 6 | ||
| 7 | 或 | |
| 8 | 20 | 无额外限制 |
样例附件:下载。