dlaud5379   1년 전

(DeepL로 영어로 번역한 텍스트를 중역했습니다. 오역이 있으면 답글로 달아주세요. 감사합니다 🙇)

문제

가로 m칸, 세로 n칸의 표가 있다. 가로줄은 위에서부터 1부터 n까지, 세로줄은 왼쪽에서부터 1부터 m까지의 번호가 붙어 있고, 위에서 i번째, 왼쪽에서 j번째에 있는 칸을 ai,j로 적는다. 이 표의 모든 칸을 순서대로 정수로 채우려고 한다. 맨 위 줄의 값은 이미 a1,1, a1,2, ..., a1,m으로 주어져 있고, 나머지 줄은 해당하는 칸에서 위로 뻗어나가는 '삼각형' 영역에 속하는 모든 칸의 합이 된다. 모든 연산은 모듈로 r로 이루어진다.

preview

ai,j의 값을 수식으로 표현하면 다음과 같다.

preview

예를 들어 가로 4칸, 세로 3칸의 표의 첫 줄이 2, 3, 4, 5이고 r = 40일 때, 완성된 표는 다음과 같다 (불필요한 모듈로 연산을 생략함).

2345
5 = 2 + 39 = 2 + 3 + 412 = 3 + 4 + 59 = 4 + 5
23 = 2 + 3 + 4 + 5 + 90 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 404 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 4033 = 3 + 4 + 5 + 12 + 9

표의 첫째 줄 (a1,1, a1,2, ..., a1,m)이 주어질 때, 마지막 줄을 구하여라. 정답에 큰 수가 등장할 수 있으므로 각 칸의 값에 모듈로 r을 취한다.

입력

첫째 줄에 n, m, r이 주어진다. (2 ≤ n, m ≤ 2,000, 2 ≤ r ≤ 109)

둘째 줄에 표의 첫째 줄을 이루는 m개의 정수 a1,1, a1,2, ..., a1,m이 순서대로 주어진다. (0 ≤ a1,i ≤ 109)

출력

표의 마지막 줄을 이루는 m개의 정수 an,1, an,2, ..., an,m을 순서대로 출력한다.

댓글을 작성하려면 로그인해야 합니다.