解説

各項を最初から順番に見ていくと、

$\begin{aligned} x_0 &= c\\ x_1 &= a c + b\\ x_2 &= a (ac + b) + b = a^2 c + (a + 1) b\\ x_3 &= a \left(a^2 c + \left(a + 1\right) b\right) + b = a^3 c + (a^2 + a + 1) b\\ &\vdots \end{aligned}$

となり、ここから $x_n = a^n c + \left(a^{n - 1} + a^{n - 2} + \cdots + a + 1\right) b$ となることがわかります。

等比数列の公式を使うと、 $x_n = a^n c + \frac{a^n - 1}{a - 1} b$ となるため、 $O(\log n)$ で計算することができます。

ただし、 $a = 1, 998244354$ のときは、 $b$ の係数の分母が $0$ になってしまうため、注意が必要です。

このような場合、 $a$ はないものとして考えると、 $x_n = c + b n$ という式を得ます。