아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

합의 합

시간 제한1초메모리 제한128 MB

요약

매 라운드마다 소가 다른 소들의 수의 합으로 자신의 수를 바꾸며 98765431로 나눈 나머지를 유지할 때, T번 반복한 뒤 각 소가 가진 수를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 행렬, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

$N$ 마리의 소가 $1$ 번부터 $N$ 번까지 번호를 달고 있습니다. 각 소 $i$ 는 처음에 정수 $C_i$ 를 가지고 있습니다. 소들은 다음 과정을 한 번의 라운드로 하여 모두 동시에 수행합니다.

각 소는 자신을 제외한 나머지 $N-1$ 마리 소가 가진 수의 합을 구합니다.
모든 소가 계산을 끝내면, 각 소는 자신의 수를 방금 구한 합으로 바꿉니다.

수가 지나치게 커지지 않도록 모든 수는 항상 98,765,431로 나눈 나머지로 관리합니다. 이 라운드를 정확히 $T$ 번 반복한 뒤, 각 소가 가진 수를 구하세요.

제약:

$1 \le N \le 50{,}000$
$0 \le C_i < 90{,}000{,}000$
$1 \le T \le 1{,}414{,}213{,}562$

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $T$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에 소 $i$ 의 시작 수 $C_i$ 가 주어집니다.

출력

$N$ 개의 줄을 출력합니다. $i$ 번째 줄에는 반복이 모두 끝난 뒤 소 $i$ 가 가진 수를 98,765,431로 나눈 나머지로 출력합니다.

힌트

다음은 예시에서 각 라운드가 끝난 뒤 소들이 가진 수를 정리한 표입니다.

          소가 가진 수
라운드   소1   소2   소3
 0        1     0     4
 1        4     5     1
 2        6     5     9
 3       14    15    11
 4       26    25    29

예제3

예제 1
입력
```
3 4
1
0
4
```
예상 출력
```
26
25
29
```
예제 2
입력
```
3 1
1
0
4
```
예상 출력
```
4
5
1
```
예제 3
입력
```
3 2
1
0
4
```
예상 출력
```
6
5
9
```

Loading...