在 这篇题解 中提到可以用 $G(x) \equiv \sqrt[k]{F(x)} \pmod{998244353}$ 转化为 $G(x) \equiv \exp (k^{-1} \ln F(x)) \pmod{998244353}$ 的做法,利用模数原根为 $3$ 使用 BSGS 求出 $F(0)$ 的 $k$ 次剩余.

这种想法是正确的,但是上文提到的那篇题解没有正确指出对于 $F(0) \equiv 3^x \pmod{998244353}$ 仅当 $\dfrac{x}{k} \bmod{998244352}$ 存在时才有 $k$ 次剩余,且代码实现也是错误的,无法通过 loj 上的多项式开三次根.

实际实现需要在 BSGS 后先特判 $k$ 是否能整除 $x$ 然后用 exgcd 求出 $k$ 在模 $998244352$ 意义下的逆元,再求出 $3^{xk^{-1}}$ 作为 $k$ 次剩余.

而 另一篇题解 也用了同样的方式,但是实现是正确的.