dokyung36d   3년 전

이 문제는 대다수가 처음 떠올리는 코드와 실제 정답 코드의 시간 복잡도는 O(n)으로 크게 다르지 않습니다.

일반적인 방식으로 할 경우 오버플로우(숫자가 너무 커짐)를 막기 위해 대다수의 분들이 계산 과정에 %p 를 이용하십니다.

그러나 모듈러(나머지)연산 곱셈의 경우 분배법칙이 성립하지만 나눗셈에서는 분배법칙이 성립하지 않습니다.

이 문제의 경우에는 p가 1000000007이나 되어 반례를 찾기 어려워 놓치기 해당 포인트를 찾기 어렵습니다.

p = 13인 경우에 6C2를 계산해보시면

(720 % 13) / ((2 % 13) * (24 % 13)) =  5 / 22로 실제 답인 2와 차이가 있습니다.

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