Introduction to Alternative Splicing

https://rosalind.info/problems/aspc/

ROSALIND | Introduction to Alternative Splicing

Problem

In “Counting Subsets”, we saw that the total number of subsets of a set SS containing nn elements is equal to 2n2n.

However, if we intend to count the total number of subsets of SS having a fixed size kk, then we use the combination statistic C(n,k)C(n,k), also written (nk)(nk).

Given: Positive integers nn and mm with 0≤m≤n≤20000≤m≤n≤2000.

Return: The sum of combinations C(n,k)C(n,k) for all kk satisfying m≤k≤nm≤k≤n, modulo 1,000,000. In shorthand, ∑nk=m(nk)∑k=mn(nk).

Sample Dataset

6 3

Sample Output

42

 

  이 문제는 앞의 Counting Subsets를 조금 더 응용하면 풀 수 있다. 앞의 문제는 0부터 n까지 조합의 개수를 구했지만 이 문제는 m부터 n까지의 조합의 개수를 구하면 된다.

def factorial(n):
    v=1
    for i in range(1,n+1):
        v*=i
    return v

N,M=map(int,input().split())
ans=0
for i in range(M,N+1):
    ans+=(factorial(N)//(factorial(i)*factorial(N-i)))

print(ans%1000000)