Description：

题意：给出 $a$ 数组，求： $$ \sum_{m=0}^nS_m(x)a_m $$ 的系数。

$1\leqslant n\leqslant 250000$

Solution：

直接用伯努利数展开： $$ \begin{align} 原式&=\sum_{m=0}^n\frac1{m+1}\sum_{k=0}^m\binom{m+1}kB_kx^{m+1-k}a_m\\ &=\sum_{m=0}^na_mm!\sum_{k=0}^m\frac{B_k}{k!}\frac{x^{m+1-k}}{(m+1-k)!}\\ &=\sum_{m=0}^na_mm!\sum_{k=1}^{m+1}\frac{B_{m+1-k}}{(m+1-k)!}\frac{x^k}{k!}\\ &=\sum_{k=1}^{n+1}\biggl(\sum_{m=k-1}^na_mm!\frac{B_{m+1-k}}{(m+1-k)!}\biggr)\frac{x^k}{k!}\\ &=\sum_{k=1}^{n+1}\biggl(\sum_{m=0}^{n-k+1}a_{m+k-1}(m+k-1)!\frac{B_m}{m!}\biggr)\frac{x^k}{k!}\\ \end{align} $$ 按照套路，设 $v[n-x]=a_xx!$ ，那么： $$ 原式：=\sum_{k=1}^{n+1}\biggl(\sum_{m=0}^{n-k+1}v[n-k+1-m]\frac{B_m}{m!}\biggr)\frac{x^k}{k!}\\ $$ 中间是一个卷积，因此可以用 $NTT$ 求。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN],v[MAXN];

int fac[MAXN],inv[MAXN];

int tmpb[MAXN],B[MAXN];

#define P 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % P)if(b & 1)res = 1ll * res * a % P;

	return res;

}

int rev[MAXN];

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

int init(int n)

{

	int l = 0,len = 1;

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

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

	return len;

}

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 * f[k + i / 2] * w % 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 c[MAXN];

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

{

	if(deg == 1)

	{

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

		return;

	}

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

	int len = init(2 * deg);

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

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

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

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

	{

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

	}

	NTT(b,len,-1);NTT(c,len,-1);

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

	return;

}

int main()

{

	scanf("%d",&n);

	fac[0] = 1;

	for(int i = 1;i <= n + 1;++i)fac[i] = 1ll * fac[i - 1] * i % P;

	inv[n + 1] = power(fac[n + 1],P - 2);

	for(int i = n;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % P;

	for(int i = 0;i <= n;++i)tmpb[i] = inv[i + 1];

	calc_inv(tmpb,B,n + 1);

	for(int i = 0;i <= n;++i)B[i] = 1ll * B[i] * fac[i] % P;

	//for(int i = 0;i <= n;++i)cout << B[i] << " ";cout << endl;

	for(int i = 0;i <= n;++i)scanf("%d",&a[i]);

	cout << a[0] << " ";

	for(int i = 0;i <= n;++i)v[n - i] = 1ll * a[i] * fac[i] % P;

	for(int i = 0;i <= n;++i)B[i] = 1ll * B[i] * inv[i] % P * power(P - 1,i) % P;

	int len = init(2 * n);

	NTT(v,len,1);NTT(B,len,1);

	for(int i = 0;i < len;++i)v[i] = 1ll * v[i] * B[i] % P;

	NTT(v,len,-1);

	for(int k = 1;k <= n + 1;++k)

	{

		int ans = 1ll * v[n - k + 1] * inv[k] % P;

		printf("%d ",ans);

	}

	cout << endl;

	return 0;

}