시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 475 | 122 | 88 | 24.929% |
다항 정리(multinomial theorem)는 다항식의 거듭제곱을 전개하는 정리이며, 전개식의 계수를 다항 계수(multinomial coefficient)라고 한다. 우리가 다룰 다항식은 모든 항의 계수가 1인 경우이고, 아래는 그 예시이다.
(1 + x + x2)3 = 1 + 3x + 6x2 + 7x3 + 6x4 + 3x5 + x6
다항정리를 일반화 하면, 다음과 같이 나타낼 수 있다.
(1 + x + ... + xn)m = a0x0 + a1x1 + ... + anmxnm
어떤 수 k(0 ≤ k ≤ n × m)가 주어졌을 때 xk의 계수 ak를 구하는 프로그램을 작성하시오.
첫 번째 줄에 음이 아닌 정수 n(0 ≤ n ≤ 500), m(1 ≤ m ≤ 500), k가 주어진다.
첫 번째 줄에 xk의 계수를 출력한다. 단, 수가 커질 수 있으므로 1,000,000,009로 나눈 나머지를 출력한다.
2 3 4
6
문제에 주어진 다항식을 푸는 방식 중 하나는 다음과 같다.
University > 한양대학교 ERICA 캠퍼스 > Zero One Algorithm Contest 2018 G번