問題一覧 > 通常問題

No.2883 K-powered Sum of Fibonacci

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : Iroha_3856Iroha_3856 / テスター : sortA0329sortA0329 tikuwa_tikuwa_ hiro1729hiro1729
3 ProblemId : 11213 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-08 08:24:42

問題文

以下のように数列 $F = (F_1, F_2, \ldots)$ を定義します。

  • $F_1 = 1$
  • $F_2 = 1$
  • $F_i = F_{i-1} + F_{i-2}\ (i \geq 3) $

正整数 $N, K$ が与えられます。

$\displaystyle \left( \sum_{i=1}^N F_i^{\ K} \right) \bmod 998244353$ を求めてください。

入力

$N\ K$

入力は全て以下の制約を満たす

  • $1 \leq N \leq 10^{18}$
  • $1 \leq K \leq 100$
  • $N, K$ は整数

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
4 3
出力
37

$F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3$ となるので、答えは $(1^3 + 1^3 + 2^3 + 3^3) \bmod 998244353 = 37$ となります。

サンプル2
入力
1 1
出力
1

$N = 1$ もしくは $K = 1$ となることもあります。

サンプル3
入力
1000000000000000000 100
出力
741845682

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。