amok   1년 전

예를 들어, 

a가 2개, b가 44개, c가 10개 d가 32423개

있다고 했을 때 이 중 2 + 44 + 10 + 32423 개(모든 것들)를 순서에 맞춰 배열하는 경우의 수는 closed form 으로 쉽게 계산할 수 있잖아요. 

(2+44+10+32423)! / (2! * 44! * 10! * 32423!) 이렇게요.

그런데 이 때 2 + 44 + 10 + 32423 개 모두를 고려하는 것이 아니라 n개만 고려하고 뽑는 순서를 고려했을 때 뽑는 방법의 수를 closed form으로 쉽게 계산할 수 있는 방법이 있나요?

(min(2, n) + 1) * (min(44, n) + 1) * (min(10, n) + 1) * (min(32423, n) + 1) 개의 상태를 갖는 동적 계획법으로 풀 수 있을 것 같은데... 그거 말고 더 빠른 방법은 없나요?


http://codeforces.com/contest/...

이 문제 보고 질문드리는데, 사실 제가 질문한 걸 빨리 구하는 방법이 아마 없을 것 같아서, 다른 방법으로 접근해야 할 것 같은데, 혹시 방법이 있나 해서 질문드립니다. 이미 저 문제 에디토리얼이 있는데 그냥 혼자 풀어보려고 안 읽고 쩔쩔매고 있는데, 저 문제 해결방법을 묻는 건 아니에요.

139   1년 전

각각에 대해 exponential generating function을 부여하고 접근하는것도 괜찮지 않을까요...!

amok   1년 전

약 1년 전에 생성함수에 대해 억지로 꾸역꾸역 공부했던 기억이 나네요. 잘 이해를 못했었는데... 아 언젠가 다시 생성함수를 다시 공부해야하는데... 언제하지...

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