#P18147. Huge Segment Tree
Huge Segment Tree
Huge Segment Tree
给定整数K。在整数轴上,称形如
$$[2^i j,\;2^i(j+1))\qquad (0\le i\le K,\ 0\le j<2^{K-i})$$的半开区间为线段树区间。
对任意整数0≤l<r≤2^K,定义f(l,r)为:用若干线段树区间的并恰好表示[l,r)时,所需区间数量的最小值。
请依次求出,对于k=1,2,…,2K−2,有多少对整数(l,r)满足0≤l<r≤2^K且f(l,r)=k。每个答案对998244353取模。
输入格式
一行一个整数K,2≤K≤500000。
输出格式
按k从1到2K−2的顺序,输出对应的2K−2个答案,以空格分隔。
样例1
输入:
3
输出:
15 14 6 1
只有(l,r)=(1,7)需要4个线段树区间。
样例2
输入:
5
输出:
63 110 132 114 70 30 8 1
样例3
输入:
10
输出:
2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1