shyou1119   1년 전

1. 메모리 초과 -> stack overflow인 경우 고려. 

2. input을 int로 받은 경우 -> overflow 때문에 int 범위 넘어가면 답이 틀립니다

3. edge case 처리

sum(b) - sum(a-1) 로 계산하는 경우 a=1일 때 sum(0)을 계산하게 되는데 이에 대한 처리

4. 마지막에 결과값 양수로 고치기

큰 수 - 작은 수가 음수가 나올 수 없지만 mod 값끼리 빼다 보니 음수가 나올 수 있습니다 

마지막에 Mod를 한 번 더해주고 Modulo 연산을 해줍니다

참고

저는 행렬 거듭제곱을 dp로 풀었는데 범위가 long long이다 보니 2의 거듭제곱 꼴만 저장해두고 2의 거듭제곱 값끼리 곱해주는 식으로 계산했습니다. (예 : A^11 = A^8 * A^2 * A^1) 

2의 거듭제곱을 판정할 때 bit shift 연산으로 했는데 bit shift도 overflow가 날 수 있다는 사실을 모르고 그냥 1 << bit 이런 식으로 사용했는데, 이렇게 하면 1을 int로 인식하고 bit가 31보다 크면 한 바퀴를 돌게 됩니다. 이를 방지하기 위해 1ll << bit로 처리해줘야 값이 long long으로 인식됩니다

댓글을 작성하려면 로그인해야 합니다.