关于常系数线性递推...

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>

typedef long long Long;
typedef double Ld;

const int N = 800000*2;
const Ld PI = acos(-1);
const int P = 998244353;
const int W = 3;

int pow(int a,int b)
{
	a %= P;
	if(a < 0)
	a += P; 
	int r = 1.;
	while(b)
	{
		if(b & 1)
		r = (1LL * r * a) % (1LL * P);
		a = (1LL * a * a) % (1LL * P);
		b >>= 1;
	}
	return r;
}

namespace NTT
{
	int wn[N + 10];
	int rev[N + 10];
	void init(int n)
	{
		int log2n = 0;
		int nn = (n >> 1);
		while(nn)
		{
			log2n ++;
			nn >>= 1;
		}

		int num = 0;
		for(int i = 1;i <= n;i <<= 1)
		{
			wn[num++] = pow(W,(P-1)/i);
		}

		int x = 0;
		int y = 0;
		for(int i = 0;i < n;i++)
		{
			x = i;
			y = 0;
			for(int j = 1;j <= log2n;j++)
			{
				y <<= 1;
				y |= (x & 1);
				x >>= 1;
			}
			rev[i] = y;
		}
	}

	int buf[N + 10];
	void NTT(int * a,int n,int s)
	{
		for(int i = 0;i < n;i++)
		buf[i] = a[rev[i]];
		for(int i = 0;i < n;i++)
		a[i] = buf[i];

		int t = 2;
		int div2 = 0;
		int l = 0;
		int num = 0;
		while(t <= n)
		{
			div2 = (t >> 1);
			l = n / t;
			int ww = wn[++num];
			if(s)
			ww = pow(ww,P-2);
			for(int i = 0;i < n;i += t)
			{
				int w = 1;
				for(int j = 0;j < div2;j++)
				{
					int x = a[i+j];
					int y = (1LL * a[i+j+div2] * w) % (1LL * P);
					a[i+j] = (x + y) % P;
					a[i+j+div2] = (x + P - y) % P;
					w = (1LL * w * ww) % (1LL * P);
				}
			}

			t <<= 1;
		}
		if(s)
		{
			int di = pow(n,P-2);
			for(int i = 0;i < n;i++)
			a[i] = (1LL * a[i] * di) % (1LL * P);
		}
	}

	void mul(int * a,int * b,int * c,int n)
	{
		init(2 * n);
		NTT(a,2 * n,0);
		NTT(b,2 * n,0);
		for(int i = 0;i < 2 * n;i++)
		c[i] = (1LL * a[i] * b[i]) % (1LL * P);
		NTT(c,2 * n,1);
	}

	int tmp[N + 10];
	void get_inv(int * a,int * b,int t)//b = a^-1 mod x^t
	{
		if(t == 1)
		{
			b[0] = pow(a[0],P-2);
			return ;
		}

		get_inv(a,b,(t + 1) >> 1);

		int k = 0;
		for(k = 1;k <= (t << 1) + 3;k <<= 1);

		for(int i = 0;i < t;i++)
		tmp[i] = a[i];
		for(int i = t;i < k;i++)
		tmp[i] = 0;

		init(k);

		NTT(tmp,k,0);
		NTT(b,k,0);

		for(int i = 0;i < k;i++)
		{
			int val = (1LL * b[i] * b[i]) % (1LL * P);
			tmp[i] = (1LL * tmp[i] * val) % (1LL * P);
		}
		NTT(tmp,k,1);
		NTT(b,k,1);

		for(int i = 0;i < k;i++)
		b[i] = (2LL * b[i] + P - tmp[i]) % P; 
		for(int i = t;i < k;i++)
		b[i] = 0;
	}
};

int pa[N + 10]; 
int a[N + 10];
int d[N + 10];//d[i] = c[i+n]
int c[N + 10];
int b[N + 10];
int p[N + 10];

int main()
{
	FILE * fin = fopen("test.in","r");
	FILE * fout = fopen("test.out","w");

	int n = 0;
	fscanf(fin,"%d",&n);

	for(int i = 1;i <= n;i++)
	{
		fscanf(fin,"%d",a + i);
		a[i] = ((a[i] % P) + P) % P;
	}

	for(int i = 0;i < 2 * n;i++)
	{
		fscanf(fin,"%d",c + i);
		c[i] = ((c[i] % P) + P) % P;
		if(i >= n)
		d[i] = c[i];
	}

	{
		for(int i = 1;i <= n;i++)
		pa[i] = -a[i];
		pa[0] ++;
		NTT::get_inv(pa,b,n);
	}

	{
		for(int i = 0;i <= (n>>1);i++)
		{
			if(i < n-i)
			b[i] ^= b[n-i] ^= b[i] ^= b[n-i];
		}

		int e = 3 * n;
		int q = 1;
		while(q <= e)
		q <<= 1;

		NTT::mul(d,b,p,q);

		for(int i = 3 * n - 1;i >= 2 * n;i--)
		{
			p[i-n] = p[i];
			p[i] = 0;
		}
	}

	{
		memset(b,0,sizeof(b));

		for(int i = 0;i <= n;i++)
		{
			if(i < 2*n-i)
			p[i] ^= p[2*n-i] ^= p[i] ^= p[2*n-i];
		}

		int e = 6 * n;
		int q = 1;
		while(q <= e)
		q <<= 1;

		NTT::mul(a,p,b,q);

		for(int i = 0;i < 2 * n;i++)
		c[i] += b[2*n-i];
	}

	for(int i = 0;i < n;i++)
	{
		if(i == n-1)
		fprintf(fout,"%d\n",((c[i] % P) + P) % P);
		else fprintf(fout,"%d ",((c[i] % P) + P) % P);
	}

	fclose(fin);
	fclose(fout);

	return 0;
}