問題一覧 > 通常問題

No.3182 recurrence relation’s intersection sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : Cafe1942 / テスター : tsunamayo123 kk2a sclara
1 ProblemId : 12341 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-06-13 19:47:28

問題文

数列 $\{a_n\}$ を次の漸化式で定義します。

$a_0 = 1$

$a_{n + 1} = Ka_n + n^K + K^n$ $(n \geq 0)$

このとき、この数列 $\{a_n\}$ の第 $L$ 項 $a_L$ から第 $R$ 項 $a_R$ までの総和を求めてください。なお、答えが非常に大きくなる可能性があるので、答えを $998244353$ で割った余りを出力してください。

制約

  • $1 \leq K \leq 100$
  • $0 \leq L \leq R \leq 10^{18}$
  • 与えられる入力はすべて整数

入力

$K$ $L$ $R$

出力

答えを $998244353$ で割った余りを出力してください。

サンプル

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

定義に基づいて計算すると、 $a_1=3,a_2=9,a_3=26,a_4=69$ です。したがって、 $a_2+a_3+a_4$ を計算して、 $104$ を出力してください。

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

サンプル3
入力
100 0 12345678901234567
出力
676403742

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