「DTOI-4」白的 Fibonacci

Luogu

IDLGP8979

Time1500ms

Memory64MB

DifficultyP7

2023多项式洛谷原创O2优化线性递推

定义 $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. $$ 给定 $F$ 递推式的各项系数和 $k, n$，请你求出 $F(k, n) \bmod 998244353$ 的值。 ## Input 第一行，两个整数 $k, n$；第二行，五个整数 $st_0, st_1, a, b, s$；第三行，$k - 1$ 个整数 $t_2, t_3, \cdots, t_k$。 ## Output 一行一个整数表示答案。 [samples] ## Note | $\textbf{Subtask}$ | $k \leq$ | $n \leq$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $100$ | $100$ | 无 | $5$ | | $2$ | $100$ | $2^{63}$ | 无 | $25$ | | $3$ | $5000$ | $2^{63}$ | $s = 1, \forall 2 \leq i \leq k, t_i = 1$ | $10$ | | $4$ | $5000$ | $2^{63}$ | 无 | $60$ | 对于 $100\%$ 的数据，$1 \leq k \leq 5 \times 10^3$，$0 \leq n \le 2^{63}$，$-998244352 \leq st_0, st_1, a, b, s, t_i \leq 998244352$。

Samples

Input #1

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

Output #1

998096342

API Response (JSON)

{
  "problem": {
    "name": "「DTOI-4」白的 Fibonacci",
    "description": {
      "content": "定义 $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)\\ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 65536
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8979"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义 $F(k, n)$ 如下：\n\n$$\nF(k,n) = \n\\left \\{\n\\begin{aligned}\n&st_0\\ && k = 1\\ \\land\\ n = 0 \\\\\n&st_1\\ && k = 1\\ \\land\\ n = 1 \\\\\n&0\\ && k > 1 \\ \\land \\ n < 0 \\\\\n&a \\times F(k, n - 1) + b \\times F(k, n - 2)\\ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments