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으로 인식됩니다
shyou1119 1년 전 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으로 인식됩니다