Description：

对于一个排列 $p$ ，如果一个区间中所有数排序后连续，那么称它为连续段，如果两个排列连续段集合相同，那么他们是等价的，输入 $n$ ，求对于每个 $m\in[1,n]$ 长度为 $m$ 的排列的等价类个数。

$1\leqslant n\leqslant 10^5$

Solution：

一些引理和定义：

引理 1 两个交集非空的连续段的并和交都是连续段。

定义 1 一个连续段是 本原连续段 当且仅当不存在一个和它互不包含且交集非空的连续段。

引理 2 每个非本原连续段必然可以表示为一段连续的本原连续段兄弟之并。

引理 3 对于一组极大的本原连续段兄弟（即某个本原连续段的所有孩子），它们中大于 $1$ 且小于总数个组成的每一段要么都是非本原连续段，要么都不是连续段。

这个的话，就是说如果 $A,B,C$ 三个兄弟本原连续段如果 $B$ 和 $C$ 并起来也是本原连续段，那么 $A$ 和 $B,C$ 并起来也是本原连续段，不然的话 $B$ 和 $C$ 就不会和 $A$ 是兄弟连续段，而是 $B\cup C$ 和 $A$ 是兄弟连续段，所以这些兄弟连续段要么只要连续都可以并起来，要么两两之间不能合并。

那么我们把儿子节点可以并起来形成非本原连续段的本原连续段称为 正本原连续段 ，否则称为 异本原连续段 ，那么有一个结论是每一个等价类都对应一个树，树的每个节点权值为 $0/1$ ，并且树的叶子个数为 $n$ ，这个还是挺显然的。

再观察一下，会发现对于一个正本原连续段，他的儿子个数至少为 $3$ ，因为一定要形成一个非本原连续段，而对于一个异本原连续段，他要么没有儿子，如果有儿子的话儿子的个数不能为 $1$ 或 $3$ ，显然不能为 $1$ ，不能为 $3$ 是因为 $3$ 的所有排列一定存在两个连续的数相邻，他们显然可以形成一个非本原连续段。可以发现满足这样的树一定对应一个等价类。

但是这样不是很好做，需要把叶子节点很少的情况稍作调整，考虑生成函数，设 $G(x)$ 表示根节点是一个异本原连续段且叶子数不少于 $4$ 的关于子树叶子节点个数的生成函数， $F(x)$ 表示其他情况关于子树叶子节点个数的生成函数即是一个叶子节点个数大于等于 $3$ 的正本原连续段或者叶子节点个数为 $2$ 的异本原连续段，这两个显然是可以合并的，即叶子节点个数大于等于 $2$ ，没有叶子的放在哪边都可以，这里放在了 $G$ ，设 $H(x)$ 表示总共的答案，显然有 $H=F+G$ 。

显然有： $$ \begin{align} G&=x+\sum_{i=4}^\infty H^i=x+\frac{H^4}{1-H}\\ F&=\sum_{i=2}^\infty H^i=\frac{H^2}{1-H} \end{align} $$ 那么我们就得到了： $$ H^4+2H^2-(x+1)H+x=0 $$ 这样我们就可以牛顿迭代了，把他带入牛顿迭代公式： $$ H=H_0-\frac{H_0^4+2H_0^2-(x+1)H_0+x}{4H_0^3+4H_0-(x+1)} $$ 于是就可以求解了，复杂度 $O(n\log n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,p;

#define MAXN 400010

int s;

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % p;

		a = 1ll * a * a % p;

		b = b >> 1;

	}

	return res;

}

bool check(int k)

{

	for(int i = 2;i * i <= (p - 1);++i)

		if((p - 1) % i == 0 && (power(k,i) == 1 || power(k,(p - 1) / i) == 1))

			return false;

	return true;

}

int G()

{

	for(int i = 1;;++i)if(check(i))return i;

}

int H[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

void NTT(int f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		int wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			int w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				int u = f[k],t = 1ll * w * f[k + i / 2] % p;

				f[k] = (u + t) % p;

				f[k + i / 2] = (u - t + p) % p;

				w = 1ll * w * wn % p;

			}

		}

	}

	if(type == -1)

	{

		int ni = power(l,p - 2);

		for(int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % p;

	}

	return;

}

int invtmp[MAXN];

void calc_inv(int deg,int a[],int b[])

{

	if(deg == 1)

	{

		b[0] = power(a[0],p - 2);

		return;

	}

	calc_inv((deg + 1) >> 1,a,b);

	int l = 0,len = 1;

	for(;len <= (deg << 1);len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(s,(p - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % p;

	for(int i = 0;i < deg;++i)invtmp[i] = a[i];

	for(int i = deg;i < len;++i)invtmp[i] = 0;

	NTT(invtmp,len,1);NTT(b,len,1);

	for(int i = 0;i < len;++i)

	{

		b[i] = (2 * b[i] % p - 1ll * invtmp[i] * b[i] % p * b[i] % p + p) % p;

	}

	NTT(b,len,-1);

	for(int i = deg;i < len;++i)b[i] = 0;

	return;

}

int inv[MAXN];

int tmp1[MAXN],tmp2[MAXN],tmp3[MAXN];

void calc(int deg,int h[])

{

	if(deg == 1)

	{

		h[0] = 0;

		return;

	}

	calc((deg + 1) >> 1,h);

	int l = 0,len = 1;

	for(;len <= (deg << 1);len = len << 1)++l;

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 0;g[1] = g[1 - len] = power(s,(p - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % p;

	NTT(h,len,1);

	for(int i = 0;i < len;++i)tmp1[i] = 0;

	for(int i = 0;i < len;++i)tmp1[i] = (tmp1[i] + 1ll * h[i] * h[i] % p * h[i] % p * h[i] % p) % p;

	for(int i = 0;i < len;++i)tmp1[i] = (tmp1[i] + 2ll * h[i] % p * h[i] % p) % p;

	NTT(h,len,-1);NTT(tmp1,len,-1);

	for(int i = 1;i < len;++i)tmp1[i] = (tmp1[i] - h[i - 1] + p) % p;

	for(int i = 0;i < len;++i)tmp1[i] = (tmp1[i] - h[i] + p) % p;

	tmp1[1] = (tmp1[1] + 1) % p;

	for(int i = deg;i < len;++i)tmp1[i] = 0;

	NTT(h,len,1);

	for(int i = 0;i < len;++i)tmp2[i] = 0;

	for(int i = 0;i < len;++i)tmp2[i] = (tmp2[i] + 4ll * h[i] % p * h[i] % p * h[i] % p) % p;

	for(int i = 0;i < len;++i)tmp2[i] = (tmp2[i] + 4ll * h[i] % p) % p;

	NTT(h,len,-1);NTT(tmp2,len,-1);

	tmp2[1] = (tmp2[1] - 1 + p) % p;tmp2[0] = (tmp2[0] - 1 + p) % p;

	memset(tmp3,0,sizeof(tmp3));

	calc_inv(deg,tmp2,tmp3);

	NTT(tmp1,len,1);NTT(tmp3,len,1);

	for(int i = 0;i < len;++i)tmp1[i] = 1ll * tmp1[i] * tmp3[i] % p;

	NTT(tmp1,len,-1);

	for(int i = 0;i < deg;++i)h[i] = (h[i] - tmp1[i] + p) % p;

	return;

}

int main()

{

	scanf("%d%d",&n,&p);

	s = G();

	calc(n + 1,H);

	for(int i = 1;i <= n;++i)printf("%d\n",H[i]);cout << endl;

	return 0;

}