행렬과 피보나치 수의 합

시간 제한5초메모리 제한512 MB

요약

지수가 등차수열로 커지는 피보나치 수와 행렬 거듭제곱의 곱을 N이 10^1000까지 갈 수 있는 경우에 대해 소수 모듈로로 합산하는 문제입니다.

난이도: 어려움10점 중 9점
유형: 행렬, 수학, 분할 정복, 정수론
정답자: 아직 제출이 없습니다

문제

\uD06C\uAE30\uAC00 $K \times K$ \uC778 \uD589\uB82C $M$ \uACFC \uC74C\uC774 \uC544\uB2CC \uC815\uC218 $N$ , $a$ , $d$ \uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uD589\uB82C $M$ \uC758 $r$ \uD589 $c$ \uC5F4 \uC6D0\uC18C\uB97C $M_{r,c}$ \uB77C\uACE0 \uD558\uC790.

\uD589\uB82C $S$ \uB97C \uB2E4\uC74C\uACFC \uAC19\uC774 \uC815\uC758\uD55C\uB2E4.

[ S = \sum_{i=0}^{N}{F_{a+i \cdot d} \cdot M^i}. ]

\uC5EC\uAE30\uC11C $M^0$ \uB294 \uB2E8\uC704 \uD589\uB82C\uC774\uB2E4. \uD53C\uBCF4\uB098\uCE58 \uC218\uB294 $F_0 = 0$ , $F_1 = 1$ \uC774\uACE0, $i > 1$ \uC77C \uB54C $F_i = F_{i-1} + F_{i-2}$ \uB85C \uC815\uC758\uD55C\uB2E4.

\uD589\uB82C $S$ \uB97C \uAD6C\uD558\uB77C.

입력

\uCCAB\uC9F8 \uC904\uC5D0 $K$ , $a$ , $d$ , $N$ \uC774 \uC8FC\uC5B4\uC9C4\uB2E4.

\uB2E4\uC74C $K$ \uAC1C\uC758 \uC904\uC5D0\uB294 \uD589\uB82C $M$ \uC758 \uC6D0\uC18C\uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uC774 \uC911 $i$ \uBC88\uC9F8 \uC904\uC5D0\uB294 $M_{i,1}$ , $M_{i,2}$ , ..., $M_{i,K}$ \uAC00 \uACF5\uBC31\uC73C\uB85C \uAD6C\uBD84\uB418\uC5B4 \uC8FC\uC5B4\uC9C4\uB2E4.

출력

\uCD1D $K$ \uAC1C\uC758 \uC904\uC5D0 \uD589\uB82C $S$ \uC758 \uC6D0\uC18C\uB97C $998244353$ \uC73C\uB85C \uB098\uB208 \uB098\uBA38\uC9C0\uB97C \uCD9C\uB825\uD55C\uB2E4.

$i$ \uBC88\uC9F8 \uC904\uC5D0\uB294 $S_{i,1}$ , $S_{i,2}$ , ..., $S_{i,K}$ \uB97C \uACF5\uBC31\uC73C\uB85C \uAD6C\uBD84\uD558\uC5EC \uCD9C\uB825\uD55C\uB2E4.

제한

$1 \le K \le 100$
$0 \le a, d \le 10^9$
$0 \le N \le 10^{1000}$
$0 \le M_{i,j} < 998244353$

예제4

예제 1
입력
```
1 0 2 4
1
```
예상 출력
```
33
```
예제 2
입력
```
2 3 4 5
1 0
0 1
```
예상 출력
```
33552 0
0 33552
```

예제 3

입력

3 23 45 107
5 7 2
1 8 9
3 4 5

예상 출력

601338635 934201293 356700741
960409891 125261415 197093893
136328022 287118456 122438416

예제 4

입력

2 1 1 10000000000
0 1
1 998244352

예상 출력

697526667 332697837
332697837 364828830