812. Dynamical Polynomials

A dynamical polynomial is a monic polynomial $f(x)$$f(x)$ with integer coefficients such that $f(x)$$f(x)$ divides $f(x^2-2)$$f(x^2-2)$.

For example, $f(x)=x^2-x-2$$f(x) = x^2 - x - 2$ is a dynamical polynomial because $f(x^2-2)=x^4-5x^2+4=(x^2+x-2)f(x)$$f(x^2-2) = x^4-5x^2+4 = (x^2 + x -2)f(x)$.

Let $S(n)$$S(n)$ be the number of dynamical polynomials of degree $n$$n$. For example, $S(2)=6$$S(2)=6$, as there are six dynamical polynomials of degree 2:

Also, $S(5)=58$$S(5)=58$ and $S(20)=122087$$S(20)=122087$.

Find $S(10000)$$S(10\,000)$. Give your answer modulo $998244353$$998244353$.

812. 壮悍多项式

若某整系数首 1 多项式 $f(x)$$f(x)$ 满足 $f(x)$$f(x)$ 整除 $f(x^2-2)$$f(x^2-2)$，则称其为壮悍多项式。

例如，$f(x)=x^2-x-2$$f(x) = x^2 - x - 2$ 是壮悍多项式，因为 $f(x^2-2)=x^4-5x^2+4=(x^2+x-2)f(x)$$f(x^2-2) = x^4-5x^2+4 = (x^2 + x -2)f(x)$。

记 $S(n)$$S(n)$ 为次数为 $n$$n$ 的壮悍多项式的个数。例如，有 6 个次数为 2 的壮悍多项式，故 $S(2)=6$$S(2)=6$：

同理亦有 $S(5)=58$$S(5)=58$ 且 $S(20)=122087$$S(20)=122087$。

求 $S(10000)$$S(10\,000)$ 模 $998244353$$998244353$ 之值。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。