seuOJ9169 - 猪分身

猪学会了分身术，他正在数轴上练习这一术法。

初始时（第 $0$ 秒），猪（相当于 $1$ 个猪分身）位于原点（ $x=0$ ）处。

$1$ 个第 $t$ 秒位于 $x=i$ 处的猪分身会在第 $t$ 秒结束后、第 $t+1$ 秒开始前消失，同时产生 $6$ 个猪分身，其中：

猪想知道，经过 $n$ 秒后，有多少个猪分身曾在 $x=n-1$ 处停留过。

形式化地，设第 $t$ 秒位于 $x=n-1$ 处的猪分身有 $f_t$ 个，求 $\sum\limits_{t=0}^nf_t$ 。

答案对 $998244353$ 取模。

我们在题目的最后给出了一定的提示。

一行一个整数 $n$ （ $2\le n\le10^{18}$ ）。

一行一个整数，表示答案对 $998244353$ 取模后的结果。

下面用 $[g_0,g_1,g_2,g_3,\cdots]$ 来表示 $x=i$ 处有 $g_i$ 个猪分身（ $i=0,1,2,3,\cdots$ ）：

所以，答案是 $0+3+4+1+0=8$ 。

252917600

设 $p$ 是正整数，容易证明：

\begin{aligned} (a+b)\bmod p&=\big((a\bmod p)+(b\bmod p)\big)\bmod p\\ (a-b)\bmod p&=\big((a\bmod p)-(b\bmod p)+p\big)\bmod p\\ (a\times b)\bmod p&=\big((a\bmod p)\times(b\bmod p)\big)\bmod p \end{aligned}

设 $b$ 是正整数，现欲求 $a^b$ 。

若 $b$ 很大，则做 $O(b)$ 次乘法是不可接受的。

设 $b$ 的二进制表示为 $\overline{c_tc_{t-1}\cdots c_0}$ ，其中 $t=\lfloor\log_2b\rfloor$ ， $c_i=\left\lfloor\dfrac{b}{2^i}\right\rfloor\bmod2$ 。

由 $a^{2^{i+1}}=a^{2^i}\times a^{2^i}$ ，先求出 $a^{2^0},a^{2^1},\cdots,a^{2^t}$ ，则

a^b=\prod_{i\in\{j\mid c_j=1\}}a^{2^i}

这样，就只需要做 $O(\log b)$ 次乘法。