luogu#P8979. 「DTOI-4」白的 Fibonacci

    ID: 12964 远端评测题 1500ms 64MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2023多项式洛谷原创O2优化线性递推

「DTOI-4」白的 Fibonacci

题目描述

定义 F(k,n)F(k, n) 如下:

$$F(k,n) = \left \{ \begin{aligned} &st_0\ && k = 1\ \land\ n = 0 \\ &st_1\ && k = 1\ \land\ n = 1 \\ &0\ && k > 1 \ \land \ n < 0 \\ &a \times F(k, n - 1) + b \times F(k, n - 2)\ && k = 1 \ \land\ n > 1 \\ &t_k \times F(k, n - 1) + s^n \times F(k - 1, n)\ && \text{otherwise} \end{aligned} \right. $$

给定 FF 递推式的各项系数和 k,nk, n,请你求出 F(k,n)mod998244353F(k, n) \bmod 998244353 的值。

输入格式

第一行,两个整数 k,nk, n

第二行,五个整数 st0,st1,a,b,sst_0, st_1, a, b, s

第三行,k1k - 1 个整数 t2,t3,,tkt_2, t_3, \cdots, t_k

输出格式

一行一个整数表示答案。

10 25
-5 -73 -95 64 15
-80 -31 -58 15 95 -1 14 -30 31 
998096342

提示

Subtask\textbf{Subtask} kk \leq nn \leq 特殊性质 分值
11 100100 100100 55
22 2632^{63} 2525
33 50005000 s=1,2ik,ti=1s = 1, \forall 2 \leq i \leq k, t_i = 1 1010
44 6060

对于 100%100\% 的数据,1k5×1031 \leq k \leq 5 \times 10^30n2630 \leq n \le 2^{63},$-998244352 \leq st_0, st_1, a, b, s, t_i \leq 998244352$。