関数で遊ぼう

任意の正の整数 $n$ に対して $f(n)=2^n$ を示す。$f(1)=2$ であり、条件より

$$f(n+1)=f(n)f(1)=2f(n)$$

が成り立つので、数学的帰納法により結論を得る。

各質問について $2^{n_i}\bmod M$ を計算すればよい。ただし $M=10^9+7$ である。 は素数で、 と互いに素なので、フェルマーの小定理により

$$2^{M-1}\equiv1\pmod M$$

である。したがって $n_i$ を $M-1=10^9+6$ で割った余りを $$ とすると、

$$2^{n_i}\equiv2^{e_i}\pmod M$$

となる。

$n_i$ は最大 $10^{200}$ なので、通常の整数型で読み込まず十進文字列として扱う。左から各桁 $d_1,d_2,\cdots,d_k$ を処理し、初期値 から

$$e\leftarrow(10e+d_j)\bmod(M-1)$$

と更新する。最後に二分累乗法で $2^e\bmod M$ を計算する。

$i$ 番目の質問の桁数を $L_i$ とすると、全体の時間計算量は $O(\sum_{i=1}^Q L_i+Q\log M)$ である。入力文字列以外の追加空間は であり、文字列の最大長は である。

Solution written by GPT6