問題一覧 > 通常問題

No.3182 recurrence relation’s intersection sum

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 50
作問者 : Cafe1942 / テスター : tsunamayo123 kk2a sclara
お気に入りにしたユーザー ProblemId : 12341 / 自分の提出
問題文最終更新日: 2025-06-13 19:47:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 470 (順位表) の他の問題:

Problem Statement

Define the sequence $\{a_n\}$ by the following recurrence relation.

$a_0 = 1$

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

Find the sum of the terms of this sequence $\{a_n\}$ from the $L$-th term $a_L$ through the $R$-th term $a_R$. Since the answer can be very large, output the answer modulo $998244353$.

Constraints

  • $1 \leq K \leq 100$
  • $0 \leq L \leq R \leq 10^{18}$
  • All input values are integers.

Input

$K$ $L$ $R$

Output

Output the answer modulo $998244353$.

Sample

Sample 1
Input
2 2 4
Output
104

Calculating from the definition gives $a_1=3,a_2=9,a_3=26,a_4=69$. Therefore, compute $a_2+a_3+a_4$ and output $104$.

Sample 2
Input
1 1 1
Output
2

Sample 3
Input
100 0 12345678901234567
Output
676403742

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