F(x) 함수가 주어지면, F'(2) 값을 구하는 문제이다.
항의 차수 expo~[1, 1e9] 항의 차수와 관계없이 무작위로 주어진다.
이 문제를 풀이하기 위해서 비트연산을 사용했다.
MSB 에서 부터 LSB 로 비교하는 방법과
LSB 에서 부터 MSB 로 비교하는 방법
두가지 방법으로 코드를 구성해 풀어보았다.
먼저 2^[1, 1e9-1] 값을 구하기 위해서
0 1 2 3 4 5 6 .... 33 까지 값을 미리 구해놓았다. 사실 31까지만 구해놓으면 문제없지만 코드 작성할 때 넉넉하게 잡았다.
v[exponent] 에 들어있는 값은 2^(2^expo) 의 값을 미리 구해놓은 것이다.
이 값은 2^(2^expo) 에서 (2^expo) 의 값을 비트연산으로 생각하고 구할 수 있기 때문에 이렇게 전처리 해놓은 것이다.
이해가 안될 수도 있어서 v[0] 부터 v[4]까지 값을 보면서 덧붙이면,
v[0] : 2^(2^0) = 2^1 = 2
v[1] : 2^(2^1) = 2^2 = 4
v[2] : 2^(2^2) = 2^4 = 16
v[3] : 2^(2^3) = 2^8 = 256
v[4] : 2^(2^4) = 2^16 = 65536
이런 식으로 값이 매겨져 있다. 그러면 식이 2^(2^expo) = 2^bit 값으로 생각할 수 있기 때문에 위와 같이 풀이 할 수 있다.
이제 이 값을 이용해서 미분했을 때 입력받은 expo 값에서 -1을 뺀 값으로 proc 함수를 사용해서 값을 받는다.
이때 앞서 말한 MSB->LSB / LSB->MSB 로 이동하면서 값을 구할 수 있다.
MSB->LSB 로 하면 upper 상한을 먼저 정한 후, 입력으로 받은 rexpo >= upper 인 경우면 빼주고 v[expo] 값을 가져와 곱해주고 % MOD 연산을 해주면 된다.
그리고 upper 값은 >> 1 비트시프트 연산으로 한 칸씩 오른쪽으로 미루고, 값이 0 이 될 때까지 진행한다. upper = upper >> 1 과 upper = upper/2 는 동일하다.
LSB->MSB 로 하면 최하위비트부터 비교를 하는 것이다. expo 값이 처음에 0부터 시작을 하며, 위와 동일하게 v[expo] 값을 가져와 곱해주고 % MOD 연산을 한다.
그리고 rexpo 값을 >> 1 하여, rexpo 값이 0이 될 때까지 진행한다.
그렇게 구한 ret 를 리턴하여 곱하는 과정을 계속 진행하면 된다.
이때 % MOD 연산을 생략한 부분이 있다면 오버플로우가 발생하거나, MOD보다 큰 값이 발생할 수도 있으므로 주의하면 될 것이라 생각한다.