题目大意

给定 $g[1], \cdots, g[m]$，求序列 $f$。

$$ f [n] = \sum_{j = 1}^n f [n - j] g [j] = \sum_{j = 1}^n f [n - j] h [j] $$

分析

不妨令 $g [0] = 0$，$h (x) = g (x) + h [0]$，我们要解方程

$$ f [n] = \sum_{j = 1}^n f [n - j] g [j] = \sum_{j = 1}^n f [n - j] h [j] $$

这个形式看似卷积，但实际上它缺了一项。对 $n > 0$ 凑卷积

$$ f [n] (h [0] + 1) = \sum_{j = 0}^n f [n - j] h [j] = (f \ast h) [n] $$

又 $f [0] = 1$，有

$$ f \ast (1 + h [0]) - f \ast h = f [0] (1 + h [0]) - f [0] h [0] = f [0] $$

解得

$$ f (x) = \frac{f [0]}{1 + h [0] - h (x)} = \frac{1}{1 - g (x)} $$

于是求逆即可

#define ACM_MOD 998244353
const int mod = ACM_MOD;

using poly_t = vector<int>;
poly_t w;

#include "template/basic/qpow.hpp"
#include "template/basic/mint.hpp"
#include "template/basic/inv.hpp"

#include "template/poly-ntt/ntt_init.hpp"
#include "template/poly-ntt/ntt.hpp"
#include "template/poly-ntt/ntt_inv.hpp"

int main() {
	int n = rr();
	int lim = getlin(n, n);
	w = ntt_init(lim);
	poly_t ans, ff(lim);

	for (int i = 1; i < n; i++)
		ff[i] = mod - rr();
	ff[0] = 1;
	ans = ntt_inv(ff, lim);
	for (int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	return 0;
}