11401번 - 이항 계수 3
이 문제는 대다수가 처음 떠올리는 코드와 실제 정답 코드의 시간 복잡도는 O(n)으로 크게 다르지 않습니다.
일반적인 방식으로 할 경우 오버플로우(숫자가 너무 커짐)를 막기 위해 대다수의 분들이 계산 과정에 %p 를 이용하십니다.
그러나 모듈러(나머지)연산 곱셈의 경우 분배법칙이 성립하지만 나눗셈에서는 분배법칙이 성립하지 않습니다.
이 문제의 경우에는 p가 1000000007이나 되어 반례를 찾기 어려워 놓치기 해당 포인트를 찾기 어렵습니다.
p = 13인 경우에 6C2를 계산해보시면
(720 % 13) / ((2 % 13) * (24 % 13)) = 5 / 22로 실제 답인 2와 차이가 있습니다.
댓글을 작성하려면 로그인해야 합니다.
dokyung36d 3년 전 6
이 문제는 대다수가 처음 떠올리는 코드와 실제 정답 코드의 시간 복잡도는 O(n)으로 크게 다르지 않습니다.
일반적인 방식으로 할 경우 오버플로우(숫자가 너무 커짐)를 막기 위해 대다수의 분들이 계산 과정에 %p 를 이용하십니다.
그러나 모듈러(나머지)연산 곱셈의 경우 분배법칙이 성립하지만 나눗셈에서는 분배법칙이 성립하지 않습니다.
이 문제의 경우에는 p가 1000000007이나 되어 반례를 찾기 어려워 놓치기 해당 포인트를 찾기 어렵습니다.
p = 13인 경우에 6C2를 계산해보시면
(720 % 13) / ((2 % 13) * (24 % 13)) = 5 / 22로 실제 답인 2와 차이가 있습니다.