본문 바로가기 메뉴 바로가기

구사과

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

구사과

검색하기 폼
  • 분류 전체보기 (341)
    • 공부 (289)
      • Problem solving (256)
      • CS theory (26)
      • Math (5)
      • 기타 (2)
    • 음악 (26)
    • 생각 (25)
  • 방명록

이항계수 (nCr) mod p 계산하기

nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n^2)위에 저 식을 그냥 구현만 해도 O(n) 인데..! 하지만 컴퓨터의 메모리는 한정되어 있으니 수를 그대로 들고 갈 수는 없고, mod p는 나눗셈을 하기 썩 좋은 상황은 아니다.그래서, nCr = (n-1)C(r-1) + (n-1)Cr 이라는 점화식(파스칼의 삼각형)을 사용해서 n^2에 계산하는 게 잘 알려져 있다. N^2 크기의 배열을 잡고 서서히 계산해 나가는 것이다. 이 방법은 나눗셈을 완전히 우회하는 방법으로써 사실 여러모로 제일 안정적인 방..

공부/Problem solving 2015. 9. 25. 23:37
Introduction to Polygon

http://evenharder.tistory.com/

공부/Problem solving 2015. 9. 18. 09:06
Wilco - Nothing'severgonnastandinmyway(Again)

(Summerteeth, 1999)

음악 2015. 9. 13. 12:31
이전 1 ··· 94 95 96 97 98 99 100 ··· 114 다음
이전 다음
공지사항
최근에 올라온 글
Total
Today
Yesterday

Blog is powered by Tistory / Designed by Tistory

티스토리툴바