题解

经典结论

$$x^k=\sum_{i=0}^k\begin{Bmatrix}k\\i\end{Bmatrix}x^{\underline i} $$

代入

$$\sum_{k=0}^{n-1}a_kx^k=\sum_{k=0}^{n-1}\sum_{i=0}^ka_k\begin{Bmatrix}k\\i\end{Bmatrix}x^{\underline i}=\sum_{i=0}^n\left(\sum_{k=i}^na_k\begin{Bmatrix}k\\i\end{Bmatrix}\right)x^{\underline i} $$

于是答案序列 $b$ 就是

$$\begin{aligned} b_k&=\sum_{i=k}^na_i\begin{Bmatrix}i\\k\end{Bmatrix}=\sum_{i=0}^na_i\begin{Bmatrix}i\\k\end{Bmatrix} \\&=\sum_{i=0}^na_i\sum_{t=0}^k\frac{t^i}{t!}\frac{(-1)^{k-t}}{(k-t)!}=\sum_{t=0}^k\frac{\sum_{i=0}^na_it^i}{t!}\frac{(-1)^{k-t}}{(k-t)!}\\&=\sum_{t=0}^k\frac{F(t)}{t!}\frac{(-1)^{k-t}}{(k-t)!} \end{aligned}$$

多点求值处理 $F(t)$ 卷积即可。

代码

const int N = 1e5 + 5, pN = N << 3;
const int mod = 998244353, G = 3, invG = 332748118;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
#define clr(f, x) memset (f, 0, sizeof(int) * (x))
#define cpy(f, g, x) memcpy (f, g, sizeof(int) * (x))
	int add(int a, int b) { return a + b > mod? a + b - mod: a + b; }
	int dec(int a, int b) { return a - b < 0? a - b + mod: a - b; }
	int mul(int a, int b) { return 1ll * a * b % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	namespace poly {
		int tr[pN];

		void init (int n, int siz) {
			for (int i = 0; i < n; ++i)
				tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (siz - 1));
		}

		void NTT (int *f, int n, int op = 1) {
			for (int i = 0; i < n; ++i)
				if (i < tr[i]) swap(f[i], f[tr[i]]);
			for (int p = 1; p < n; p <<= 1) {
				int omega = qpow (op? G: invG, (mod - 1) / (p << 1));
				for (int j = 0; j < n; j += p << 1)
					for (int w = 1, k = 0; k < p; k++, w = mul(w, omega)) {
						int x = f[j | k], y = mul(w, f[j | k | p]);
						f[j | k] = add(x, y), f[j | k | p] = dec(x, y);
					}
			}
			if (!op) {
				int invn = qpow(n, mod - 2);
				for (int i = 0; i < n; i++) f[i] = mul(f[i], invn);
			}
		}
		void px(int *f, int *g, int lim) { for (int i = 0; i < lim; ++i) f[i] = mul(f[i], g[i]); }
		void times(int *f, int *g, int n, int m, int T) {
			int lim = 1, lsiz = 0; for (; lim < n + m; lim <<= 1, lsiz++);
			init(lim, lsiz);
			static int tmp[pN]; clr(f + n, lim - n), cpy (tmp, g, m), clr(tmp + m, lim - m);
			NTT(f, lim), NTT(tmp, lim); px(f, tmp, lim); NTT(f, lim, 0);
			clr (f + T, lim - 1), clr (tmp, lim);
		}
		void inv (int *f, int n) {
			static int g[pN], r[pN], tmp[pN];
			g[0] = qpow(f[0], mod - 2);
			int lim = 1, lsiz = 0;
			for (int len = 2; (len >> 1) <= n; len <<= 1) {
				lim = len, lsiz++; init(lim, lsiz);
				cpy(r, g, len >> 1); cpy(tmp, f, lim);
				NTT(tmp, lim); NTT(r, lim); px(r, tmp, lim); NTT(r, lim, 0); clr(r, len >> 1);
				cpy(tmp, g, len); 
				NTT(tmp, lim); NTT(r, lim); px(r, tmp, lim); NTT(r, lim, 0);
				for (int i = (len >> 1); i < len; ++i) g[i] = dec(mul(g[i], 2), r[i]);
			}
			cpy(f, g, n); clr(g, lim); clr(r, lim); clr(tmp, lim);
		}
		void div (int *f, int *g, int n, int m) {
			static int fR[pN], gR[pN];
			int L = n - m + 1;
			reverse(f, f + n); cpy(fR, f, L); reverse(f, f + n);
			reverse(g, g + m); cpy(gR, g, L); reverse(g, g + m);
			inv(gR, L); times(gR, fR, L, L, L); reverse(gR, gR + L);
			times(g, gR, n, n, n);
			for (int i = 0; i < m - 1; i++) g[i] = dec(f[i], g[i]);
			clr (g + m - 1, L);
			cpy(f, gR, L); clr(f + L, n - L);
		}
		void mof (int *f, int *g, int n, int m) {
			static int fR[pN], gR[pN];
			int L = n - m + 1;
			reverse(f, f + n); cpy(fR, f, L); reverse(f, f + n);
			reverse(g, g + m); cpy(gR, g, L); reverse(g, g + m);
			inv(gR, L); times(gR, fR, L, L, L); reverse(gR, gR + L);
			times(gR, g, L, m, m - 1);
			for (int i = 0; i < m - 1; i++) f[i] = dec(f[i], gR[i]);
			clr (f + m - 1, L); clr(gR, n); clr(fR, n);
		}
	}
	namespace Evaluation {
		using namespace poly;
		int gl[20][pN];
		void prework (int dep, int l, int r) {
			if (l == r) {
				gl[dep][l << 1] = mod - l;
				gl[dep][l << 1 | 1] = 1;
				return;
			}
			int mid = (l + r) >> 1;
			prework(dep + 1, l, mid);
			prework(dep + 1, mid + 1, r);
			cpy(&gl[dep][l << 1], &gl[dep + 1][l << 1], mid - l + 2);
			times(&gl[dep][l << 1], &gl[dep + 1][(mid + 1) << 1], mid - l + 2, r - mid + 1, r - l + 2);
		}
		int s1[pN], s2[pN];
		void solve (int dep, int l, int r, int *f, int *y) {
			if (r - l <= 350) {
				for (int i = l; i <= r; ++i) {
					int buf = 1;
					for (int j = l + l; j < l + r + 1; ++j) {
						y[i] = add(y[i], mul(buf, f[j]));
						buf = mul(buf, i);
					}
				}
				return;
			}
			int mid = (l + r) >> 1;
			cpy(s1, &f[l << 1], r - l + 1); mof(s1, &gl[dep + 1][l << 1], r - l + 1, mid - l + 2);
			cpy(s2, &f[l << 1], r - l + 1); mof(s2, &gl[dep + 1][(mid + 1) << 1], r - l + 1, r - mid + 1);
			for (int i = (l << 1); i < (r << 1 | 1); i++) f[i] = 0;
			cpy(&f[l << 1], s1, mid - l + 1);
			cpy(&f[(mid + 1) << 1], s2, r - mid);
			clr(s1, r - l + 1); clr(s2, r - l + 1);
			solve(dep + 1, l, mid, f, y);
			solve(dep + 1, mid + 1, r, f, y);
		}
		void eval (int *f, int *y, int n, int m) {
			prework(0, 0, m - 1);
			if (n > m) mof(f, gl[0], n, m + 1);
			solve(0, 0, m - 1, f, y);
		}
	}
	int n, m;
	int fac[N], inv[N];
	void init(int n) {
		inv[1] = inv[0] = fac[0] = 1;
		for (int i = 1; i <= n; i++) fac[i] = mul(fac[i - 1], i);
		for (int i = 2; i <= n; i++)
			inv[i] = mul(inv[mod % i], mod - mod / i);
		for (int i = 2; i <= n; i++) inv[i] = mul(inv[i], inv[i - 1]);
	}
	int f[pN], g[pN], h[pN];
	int main () {
		n = Read(); init(n);
		for (int i = 0; i < n; i++) f[i] = Read();
		for (int i = 0; i < n; i++) g[i] = i;
		Evaluation::eval(f, h, n, n);
		for (int i = 0; i < n; i++) h[i] = mul(h[i], inv[i]), g[i] = (i & 1)? (mod - inv[i]): inv[i];
		poly::times(g, h, n, n, n);
		for (int i = 0; i < n; i++) printf ("%d ", g[i]); putchar(10);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}