Description：

$n\times n$ 的网格摆 $n$ 个物品，每行每列摆一个。摆放完后每一时刻，如果一个格子没有物品，但若其上下左右相邻的四个格子中至少有两个格子存在物品，则这个格子便会有物品。求有多少种摆放方式最后所有的格子都有了物品。

$1\leqslant n\leqslant 500000$

Solution：

通过找规律可以发现一种摆放方式是合法的要么 $n=1$ 要么他可以表示为沿对角线依次排列的多个合法的摆放方式，也就是说可以沿对角线把他划分成多个合法的摆放，那么我们设 $G$ 表示沿某个对角线依次排列的方案数， $F$ 表示原问题的方案数，那么显然 $F[0]=G[0]=0,F[1]=G[1]=1,G(n)=2\times F[n](n\geqslant 2)$ ，然后我们还能发现我们可以把一个 $G$ 旋转 $90^\circ$ 放在一个角，作为最小的不能划分的部分，其他的可以随意划分，这样保证了计数的不重不漏，因此有： $$ G[n]=\sum_{i=0}^nG[i]\times F[n-i](n\geqslant 2) $$ 那么我们可以列出两个 $G$ 和 $F$ 生成函数的等式，然后联立可以解出一个只与 $F$ 有关的二次方程，最后直接对它牛顿迭代就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

#pragma GCC optimize(3)

inline int rd()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

using namespace std;

int n;

#define P 998244353

#define MAXN 1050010

#define INV2 499122177

int a[MAXN];

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

int rev[MAXN];

#define R register

inline int power(int a,int b)

{

	R int res = 1;

	while(b > 0)

	{

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

		a = 1ll * a * a % P;

		b = b >> 1;

	}

	return res;

}

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

{

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

	{

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

	}

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

	{

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

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

		{

			R int w = 1;

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

			{

				R 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)

	{

		R int ni = power(l,P - 2);

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

	}

	return;

}

inline int init(int deg)

{

	R int l = 0,len = 1;

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

	for(R 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(3,(P - 1) / len);

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

	return len;

}

int invtmp[MAXN];

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

{

	if(deg == 1)

	{

		b[0] = P - 1;

		return;

	}

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

	R int len = init(deg);

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

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

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

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

	{

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

	}

	NTT(b,len,-1);

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

	return;

}

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

int fc2[MAXN],fz[MAXN],fm[MAXN],tmp[MAXN];

void calc(int f[],int deg)

{

	if(deg == 1)return;

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

	R int len = init(deg);

	for(R int i = 0;i < deg;++i)fm[i] = 2 * f[i] % P;

	fm[1] = (fm[1] + 1) % P;fm[0] = (fm[0] - 1 + P) % P;

	for(R int i = 0;i < deg;++i)tmp[i] = 0;//cout << "st" << endl;

	inv(fm,tmp,deg);//cout << "ed" << endl;

	for(R int i = 0;i < deg;++i)f[i] = 1ll * f[i] * INV2 % P;

	for(R int i = 0;i < deg;++i)fz[i] = (f[i] - f[i - 1] + P) % P;

	fz[1] = (fz[1] - 1 + P) % P;

	NTT(fz,len,1);NTT(tmp,len,1);

	for(R int i = 0;i < len;++i)fz[i] = 1ll * fz[i] * tmp[i] % P;

	NTT(fz,len,-1);

	for(R int i = deg;i < len;++i)fz[i] = tmp[i] = 0;

	for(R int i = 0;i < deg;++i)f[i] = (f[i] + fz[i]) % P;

	return;

}

int F[MAXN];

int main()

{

	freopen("grid.in","r",stdin);

	freopen("grid.out","w",stdout);

	scanf("%d",&n);

	R int mx = 0;

	for(R int i = 1;i <= n;++i)a[i] = rd();

	for(R int i = 1;i <= n;++i)mx = max(mx,a[i]);

	calc(F,mx + 1);

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

	fclose(stdin);

	fclose(stdout);

	return 0;

}