33723번 - [F] Functional Sequence 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 51 | 26 | 16 | 66.667% |
문제
하바는 최근 학교에서 수열과 함수에 대해 배웠다. 배운 것을 바로 적용하는 성격의 하바는 아래와 같이 길이 $N$의 수열 $A$를 받아서 길이 $N$의 수열 $D$를 반환하는 함수 $d(A)$를 만들었다.
- $D_0=A_0$이다.
- $0<i<N$인 $i$에 대해 $D_i=A_{i}-A_{i-1}$이다.
하지만 이 함수를 가지고 놀던 하바는 함수를 여러 번 적용할 수 있다는 것을 깨닫고, 아래와 같이 길이 $N$의 수열 $A$를 받아서 길이 $N$의 수열 $B$를 반환하는 함수 $f(A)$를 만들었다.
- $0\le i<N$인 $i$에 대해 $B_{i}=(d^{i}(A))_i$이다.
$d^i$가 무엇을 의미하는지 모른다면 하단의 노트를 참고하자.
이제 조금 더 재밌는 함수를 가진 하바는 가지고 있던 수열 $A$에 함수 $f$를 $K$번 적용하여 $B=f^{K}(A)$를 만들었다.
수열 $B$와 함수를 적용한 횟수 $K$가 주어질 때 하바가 가지고 있던 수열 $A$를 추정해 보자.
입력
첫째 줄에는 하바가 만든 수열 $B$의 길이 $N$과 하바가 함수를 적용한 횟수 $K$가 공백으로 구분되어 주어진다. $(1 \le N \le 5\,000;$ $0 \le K \le 10^9)$
둘째 줄에는 수열 $B$의 원소 $B_0$, $B_1$, $\ldots$, $B_{N-1}$이 공백으로 구분되어 주어진다. $(0 \le B_{i} \le 10^9)$
출력
만약 조건을 만족하는 수열 $A$가 존재하지 않는다면 첫째 줄에 -1을 출력한다.
만약 조건을 만족하는 수열 $A$가 존재한다면 첫째 줄에 수열 $A$의 각 원소 $A_0$, $A_1$, $\ldots$, $A_{N-1}$을 $10^9 + 7$로 나눈 나머지를 공백으로 구분하여 출력한다.
만약 가능한 수열이 여러 가지라면 그중 아무거나 하나를 출력한다.
예제 입력 1
5 2 1 2 15 134 1613
예제 출력 1
1 4 27 256 3125
$A = [1, 4, 27, 256, 3125]$라고 하자. 그러면 함수를 $1$번 적용한 결과는 $f(A) = [1, 3, 20, 186, 2248]$이 되고, 여기에 함수를 $1$번 더 적용하면 $B = f(f(A)) = [1, 2, 15, 134, 1613]$이 된다.
예제 입력 2
4 0 1 2 1 7
예제 출력 2
1 2 1 7
노트
어떠한 함수 $f$에 대해 $f^{n}$은 다음과 같이 정의한다.
- $f^{0}(X) =X$다.
- $f^{n}(X) =f(f^{n-1}(X))$다.
출처
- 문제를 ���든 사람: hibye1217
- 문제를 검수한 사람: minjunnick, mujigae, pyb1031, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호