시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1016 | 437 | 318 | 43.562% |
1부터 T까지의 범위에 있는 수들이 총 A개 있다. 이들 중 K개를 골라서 집합을 만들 때, 가능한 집합의 개수를 세려 한다. 단, K의 범위는 1 ≤ S ≤ K ≤ B ≤ A로 한다. 즉, 두 정수 S, B를 입력받아서 K = S일 경우, …, K = B일 경우의 집합의 개수를 모두 더하려고 한다.
예를 들어 T=3, 수들이 1, 1, 2, 2, 3인 경우를 생각해 보면, 각기 다음의 경우가 있다.
따라서 S = 2, B = 3일 경우의 답은 10이 된다.
우리가 일반적으로 이야기하는 집합은 같은 원소를 허용하지 않는다. 이 문제에서의 집합은 같은 원소가 없다는 사실 보다는, 집합의 각 원소들의 순서를 바꾸어도 같은 집합이라는 사실에 주목하여 풀도록 한다. 즉, {1, 1, 2}는 하나의 집합이고, {1, 2, 1}은 이와 같은 집합이다.
첫째 줄에 네 정수 T, A, S, B가 주어진다. 다음 줄에는 A개의 수가 차례로 주어진다.
첫째 줄에 답을 1,000,000으로 나눈 나머지를 출력한다.
3 5 2 3 1 2 2 1 3
10