[질문] nCr 젤빠른 알고리즘이 이거맞음?

[익명(14.43)]

왜 예제 틀리지 ㅋㅋ

[익명(58.143)]

그렇게 하면 숫자가 mod넘어가는 순간 r로 안나눠지는경우가 생김

[익명(121.177)]

아 그렇네

[익명(220.122)]

저거 조합 공식 대입만 해봐도 아니지않음? - dc App

[익명(121.177)]

mod빼면 맞지않아?

[익명(220.122)]

아 ㅈㅅ 재귀라서 dp로 한줄 알았네 저렇게 할거면 나눗셈 연산을 페르마 소정리 써서 모듈러 역원을 곱해주는 방법으로 우회가능함 - dc App

[익명(115.40)]

몇일전에 공부했었는데 mod연산하는 숫자가 소수일 경우 페르마의 소정리 쓰시면 됩니다!

[익명(223.38)]

n! 을 n sqrt n log n에 구하는게 제일 빠름