i001. N項的費氏數列 ꝏ Extreme
標籤 : 數學
通過比率 : 2人/4人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-02-11 19:38

內容

原題

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

$\text{Waimai}$:「你是誰,我怎麼一醒來就在這裡了?」

【▅﹌€$﹌:「你現在被困在我的基地裡,如果你想離開,就必須幫我找出 $\lim\limits_{k\to\infty}t_k$ 是多少。」

$\text{Waimai}$:「我怎麼會知道,而且你不是可以 $O(-48763)$ 求出來嗎?」

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

$\text{Waimai}$:「你能不能給我一個比較簡單的問題啊?」

【▅﹌€$﹌:「好吧,現在我有一個數列 $f$,已知這個數列前 $n$ 項 $f_1\sim f_n$ 的數值,當 $i>n$ 時,$f_i = \sum\limits_{j = 1}^n a_j\times f_{i - j}$,請你求出 $f_k$ $(\bmod 998244353)$。」

$\text{Waimai}$:「好難喔$\sim$」

為了幫助 $\text{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\ (\bmod 998244353)$。

範例輸入 #1
3 2
2 3 5
5 5 1
範例輸出 #1
3
範例輸入 #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
提示 :

$10\%:n \leq 100$

$90\%:無特別限制$

標籤:
數學
出處:
Caido [管理者: becaido (Caido) ]

本題狀況 本題討論 排行

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