함수야 놀자

먼저 자연수 $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)$$

처음에는 $e=0$으로 둔다. 마지막으로 이진 거듭제곱으로 $2^e\bmod M$을 구한다.

$Q$개 질의의 자릿수 길이를 각각 $L_i$라고 하면 전체 시간 복잡도는 $O(\sum_{i=1}^Q L_i+Q\log M)$이고, 문자열 저장을 제외한 추가 공간은 이다. 입력 문자열 최대 길이는 이다.

Solution written by GPT6