和函数一起玩

首先证明，对任意正整数 $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$$

因此，设 $e_i$ 为 $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