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 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)
'문제해결(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 |