i001. N項的費氏數列 ꝏ Extreme - 高中生程式解題系統

內容

【▅﹌€＄﹌：「你現在可能已經看過了我很多的題目，但也許有很多原因，你不想寫，我也能夠瞭解，但是你知道現在這個式子 $t_{i} = t_{i - 1} + t_{i - 2}$ 只要 $O (- 48763)$ 就能求出來了嗎，雖然我不是數學家，但這聽起來還不錯對吧！」

$Waimai$ ：「你是誰，我怎麼一醒來就在這裡了？」

【▅﹌€＄﹌：「你現在被困在我的基地裡，如果你想離開，就必須幫我找出 $lim_{k \to \infty} t_{k}$ 是多少。」

$Waimai$ ：「我怎麼會知道，而且你不是可以 $O (- 48763)$ 求出來嗎？」

【▅﹌€＄﹌：「只要我求出 $t_{i}$ ，時間就會倒流 $i \times 48763$ 個單位，如果我求出了 $lim_{k \to \infty} t_{k}$ ，那就會回到宇宙還沒形成的時候，我們就不會存在了。」

$Waimai$ ：「你能不能給我一個比較簡單的問題啊？」

【▅﹌€＄﹌：「好吧，現在我有一個數列 $f$ ，已知這個數列前 $n$ 項 $f_{1} \sim f_{n}$ 的數值，當 $i > n$ 時， $f_{i} = \sum_{j = 1}^{n} a_{j} \times f_{i - j}$ ，請你求出 $f_{k}$ $(mod 998244353)$ 。」

$Waimai$ ：「好難喔 $\sim$ 」

為了幫助 $Waimai$ 逃離【▅﹌€＄﹌的基地，請你幫幫他求出答案。

輸入說明

第一行有兩個正整數 $n, k$ 代表已知 $f$ 的前 $n$ 項，和想要求 $f_{k}$ 。

第二行輸入 $n$ 個整數 $f_{1} \sim f_{n}$ 。

第三行輸入 $n$ 個整數 $a_{1} \sim a_{n}$ 。

$1 \leq n \leq 2000$
$1 \leq k \leq 10^{9}$
$0 \leq f_{i}, a_{i} < 998244353$

輸出說明

輸出一個整數代表 $f_{k} (mod 998244353)$ 。

範例輸入 #1

3 2
2 3 5
5 5 1

範例輸出 #1

範例輸入 #2

10 123456
993434526 115786751 909274645 291200609 583272460 8995920 693724184 620391611 620500364 629421350
173514742 340871210 428696360 699288680 376229141 230857339 741135603 4069552 791628677 432115064

範例輸出 #2

632609565

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (1%): 3.0s , <1K
不公開測資點#1 (1%): 3.0s , <1K
不公開測資點#2 (2%): 3.0s , <1K
不公開測資點#3 (2%): 3.0s , <1K
不公開測資點#4 (2%): 3.0s , <1M
不公開測資點#5 (2%): 3.0s , <1M
不公開測資點#6 (22%): 3.0s , <1M
不公開測資點#7 (22%): 3.0s , <1M
不公開測資點#8 (23%): 3.0s , <1M
不公開測資點#9 (23%): 3.0s , <1M

提示：

$10 % ： n \leq 100$

$90 % ：無特別限制$

標籤:

數學

出處:

Caido [管理者： beckzerojudge@gmail.com

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」