G - Sum of Fibonacci Sequence
Editorial
/
よって, $d_{4, 7} = 176$ となり, これが答えとなります。
問題文担当者:square1001


Time Limit: 2 sec / Memory Limit: 256 MB
配点: $1400$ 点
E869120は, この数列を使って次のように数列 $d_1, d_2, d_3, \dots , d_n$ を定義することにしました。
整数 $n, m$ が与えられます。そのとき, $d_{n, m}$ の値を求めてください。
ただし, 答えが非常に大きくなることがあるので, $998,244,353$ で割った余りを求めてください。
あなたはこの問題が解けますか???
問題文
次のような数列があります。- $a_1=a_2=1$, $a_{k+2}=a_{k+1}+a_k \ (k \ge 1)$
E869120は, この数列を使って次のように数列 $d_1, d_2, d_3, \dots , d_n$ を定義することにしました。
- $d_{1, j} = a_j$
- $d_{i, j} = \sum_{k = 1}^j d_{i - 1, k} \ (i \ge 2)$
整数 $n, m$ が与えられます。そのとき, $d_{n, m}$ の値を求めてください。
ただし, 答えが非常に大きくなることがあるので, $998,244,353$ で割った余りを求めてください。
あなたはこの問題が解けますか???
入力
入力は以下の形式で標準入力から与えられる。$n \quad m$
- 1行目には, 整数 $n, m$ が空白区切りで与えられる。
出力
- $d_{n, m}$ を $998,244,353$ で割った余りを求めなさい。
制約
- $1 \le n \le 200,000$
- $1 \le m \le 10^{18}$
小課題
小課題1 [ $100$ 点 ]- $1 \le n, m \le 3,000$ を満たす。
- $1 \le m \le 200,000$ を満たす。
- $1 \le n \le 3$ を満たす。
- $1 \le n \le 1000$ を満たす。
- 追加の制約はない。
入力例1
4 7
出力例1
176以下のような数列になっています。
$d_{i, 1}$ | $d_{i, 2}$ | $d_{i, 3}$ | $d_{i, 4}$ | $d_{i, 5}$ | $d_{i, 6}$ | $d_{i, 7}$ | |
$d_1$ | 1 | 1 | 2 | 3 | 5 | 8 | 13 |
$d_2$ | 1 | 2 | 4 | 7 | 12 | 20 | 33 |
$d_3$ | 1 | 3 | 7 | 14 | 26 | 46 | 79 |
$d_4$ | 1 | 4 | 11 | 25 | 51 | 97 | 176 |
よって, $d_{4, 7} = 176$ となり, これが答えとなります。
入力例2
12 20
出力例2
174174144
入力例3
16 30
出力例3
102292850$d_{16, 30} = 1,193,004,294,685$ なので, これを $998,244,353$ で割った余りは $102,292,850$ です。