i002: N項的費氏數列 ꝏ Ę̴͖̭̈̄̐̍͌͞x҉̢̠̮̝͛́̀̽͝t̵̡̥͍͓̖̊̃̄͑̕r̸̢̘͈̱̬͈̒͒̄͡e҉̧̪̬͈́̒̄̕m̸̢͎̱̗̝͚̾͆͠e҉̛͚̮̤̾̏̋͢
Tags : 數學
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-30 23:15

Content

原題

$\text{Waimai}$:「給你一個問題。」

$\text{W̴a̸i̷m̸a̷i̴}$:「有一個數列 $f$。」

$\text{W̶̨͉̳̤̼̓̇͂̃a̷̭͕͕̍͜i̴͙̗̣͎͓̊̚m̴̛̱̹̤͂̓̒͜͠a̷̭͑ḯ̶̮̉̔}$:「已知這個數列前 $n$ 項 $f_1\sim f_n$ 的數值。」

$\text{W̴̧̛̯̖͚͖̹̞̙͔̮̜̬͆̑͑̉̌̒̏̍͠ȧ̴̪͎̯̯͈̙͔͑̈́̓̎̽͜͝i̴̥̭͐͛̀̉̄͆̔̍̿m̵̬̘͂̈́ą̵̢̘̣͕̪͉̗̝̲̘͚̻̞̏̅̂̆̓͛̐̔i̸̤̙̮̬̼͎͇͍̖͗̋͂̃̈̆̄̈́͒ͅ}$:「當 $i>n$ 時,$f_i = \sum\limits_{j = 1}^n a_j\times f_{i - j}$。」

$\text{Ẉ̶̢̨̨̢̨̡̡̧̢̛̳͎̫͔͓͍̮̦̺̜̭͎̱̞̼͇̪̤̤̲͇̰̭͈̯̪̪̰̜̞̻̮̬̰͈̱̋̿͌̋́̋̍͆͆̇̊̓͋̓͋̑̂̓̅̊͊́̄͒͋̀̇̎̈́̋̊͋̈́̌̓̽͜͝͝ą̷̥̱̪͕̪̟̦̩̣͙̗̺͕͈̻̺̞͉͔̼̖̘̪̍̿̚͜ͅi̴͓̭͎̻͈̙͇̣͖̮̞͍͚̮̖̖̭͔̱̟͎̹̘̲̯͕͚̩̳͉͓̯̰̟͎̙͈͋̾̅͆̉̈̉̑̓̈́̇̈́̈́́̉͊̏̍̄̇̌̆̏̚̕͘͘̚̚m̵̢̼̖̦̗̟̉̌̀̀̏̀́̈̾̀̐̕͘ͅą̴̧̨̡̢̢̹̦̲͔̳̲̮̣̙̭͔̩͖̻̩̱̺̺̝̜͙̻̬̟͉̥̝̩͔͕̙̺͚̻̥̬̭̝͎̤̫͕͍̪͂̃̑̓̄̈͆͜͝į̴̧̙͙̖̲͙̱̫̪̜̐͆̐͗͑́̾̂͆̑̊̋̒̎̈́̏̆̅́͑̉̾̉͑̇͐͛͊̍̍͗̂̒͆͌̚̕̚͠͝͝͝}$:「請你求出 $f_k$。」

$\text{ }$:「不過因為答案可能會很大,請 $\bmod 998244353$ 後再輸出。」

Input

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

第二行輸入 $n$ 個整數 $f_1\sim f_n$。

第三行輸入 $n$ 個整數 $a_1\sim a_n$。

  • $1 \leq n \leq 3\times 10^4$
  • $1 \leq k \leq 10^9$
  • $0 \leq f_i, a_i < 998244353$
Output

輸出一個整數代表 $f_k\ (\bmod 998244353)$。

Sample Input #1
3 2
2 3 5
5 5 1
Sample Output #1
3
Sample Input #2
10 123456
993434526 115786751 909274645 291200609 583272460 8995920 693724184 620391611 620500364 629421350
173514742 340871210 428696360 699288680 376229141 230857339 741135603 4069552 791628677 432115064
Sample Output #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 (5%): 3.0s , <1M
不公開 測資點#7 (5%): 3.0s , <1M
不公開 測資點#8 (20%): 3.0s , <1M
不公開 測資點#9 (20%): 3.0s , <1M
不公開 測資點#10 (20%): 3.0s , <1M
不公開 測資點#11 (20%): 3.0s , <1M
Hint :

$10\%:n \leq 100$

$10\%:n\leq 2000$

$80\%:無特別限制$

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


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」