Baekjoon Online Judge #13279: 곱의 합 쿼리 (URL)
13279번: 곱의 합 쿼리
첫째 줄에 N(1 ≤ N ≤ 30000) 이 주어지고, 둘째 줄에는 수열에 포함되어 있는 수 Ai(1 ≤ Ai ≤ 100,000)가 주어진다. 셋째 줄에는 쿼리의 개수 Q(1 ≤ Q ≤ N)가 주어지고, 넷째 줄부터 Q개의 줄에는 각
www.acmicpc.net
Problem (문제 원문)
N개의 수로 이루어진 수열 A가 주어진다.
이때, Q개의 쿼리를 실행한 결과를 구하는 프로그램을 작성하시오.
각각의 쿼리는 정수 K로 이루어져 있다.
수열 A의 부분 수열 중에서 크기가 K인 것을 모두 구한 다음, 각 부분 수열에 들어있는 수의 곱을 구한다.
그 다음 이 수의 합을 100003로 나눈 나머지를 출력한다.
수열 A의 크기가 K인 부분 수열의 개수는 N Choose K개이다.
Restrictions (제약사항)
시간 제한: 2초
메모리 제한: 512MB
Input (입력)
첫째 줄에 N(1 ≤ N ≤ 30000) 이 주어지고, 둘째 줄에는 수열에 포함되어 있는 수 Ai(1 ≤ Ai ≤ 100,000)가 주어진다.
셋째 줄에는 쿼리의 개수 Q(1 ≤ Q ≤ N)가 주어지고,
넷째 줄부터 Q개의 줄에는 각 쿼리에 해당하는 K(1 ≤ K ≤ N)가 주어진다.
Output (출력)
각각의 쿼리에 대해서 정답을 출력한다.
Examples (예제)
| Input | Output |
| 3 1 2 3 2 1 2 |
6 11 |
| 3 1 2 2 1 2 |
8 |
Design (프로그램 설계)
Algorithm Category (알고리즘 분류)
Dynamin Programming (DP) (동적 프로그래밍) (URL) (\(O(n^2)\))
[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍
Dynamic Programming (DP) 동적 프로그래밍 - 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 구조에 적용할 수 있는 알고리즘을 통칭하는 말이다. - 특히 이러한 "작은 문제의 해답"을 Optima
dad-rock.tistory.com
FFT (Fast Fourier Transform) (고속 푸리에 변환 알고리즘) (URL) (\(O(n\log n)\))
Fast Fourier transform - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search O(N logN) divide-and-conquer algorithm to calculate the discrete Fourier transforms An example FFT algorithm structure, using a decomposition into half-size FFTs A discrete Fourier ana
en.wikipedia.org
Implementations (구현)
* GitHub (URL)
GitHub - ByeongHeonLee/Algorithms: Implementation of fundamental algorithms
Implementation of fundamental algorithms. Contribute to ByeongHeonLee/Algorithms development by creating an account on GitHub.
github.com
Performance (성능)
성공..!
