문제해결(PS)/ROSALIND

Introduction to Alternative Splicing

곰탱이장 2024. 9. 17. 16:50

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

 

ROSALIND | Introduction to Alternative Splicing

It appears that your browser has JavaScript disabled. Rosalind requires your browser to be JavaScript enabled. Introduction to Alternative Splicing solved by 1819 2012년 12월 4일 7:05:39 오전 by Rosalind Team Topics: Combinatorics The Baby and the Bat

rosalind.info

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 0mn20000≤m≤n≤2000.

Return: The sum of combinations C(n,k)C(n,k) for all kk satisfying mknm≤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)

'문제해결(PS) > ROSALIND' 카테고리의 다른 글

Expected Number of Restriction Sites  (0) 2024.09.18
Edit Distance  (1) 2024.09.17
Counting Subsets  (0) 2024.09.17
Matching Random Motifs  (0) 2024.09.16
Reversal Distance  (1) 2024.09.16