No.978 Fibonacci Convolution Easy
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 247
作問者 :
keymoon
/ テスター :
tarattata1
タグ : / 解いたユーザー数 247
作問者 :
keymoon
/ テスター :
tarattata1
問題文最終更新日: 2020-01-30 13:22:00
問題文
数列 $a$ を $a_1=0,a_2=1,a_{n}=p \cdot a_{n-1} + a_{n-2}(3 \leq n)$ で定義します。
このとき、 $\sum_{i=1}^N\sum_{j=1}^i a_i \cdot a_j$ を $1000000007$ で割った余りを計算してください。
入力
$N\ p$
- $1 \leq N \leq 2 \cdot 10^6$
- $1 \leq p \leq 10^9$
- 入力は全て整数である。
出力
$\sum_{i=1}^N\sum_{j=1}^i a_i \cdot a_j$ を $1000000007$ で割った余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 3
出力
13
数列 $a$ は $0\ 1\ 3\ 10 \cdots$ と続きます。 ここで求めるべきは $a_1 \cdot a_1 + a_2 \cdot a_1 + a_2 \cdot a_2 + a_3 \cdot a_1 + a_3 \cdot a_2 + a_3 \cdot a_3$ なので、 $0 + 0 + 1 + 0 + 3 + 9 = 13$ となります。
サンプル2
入力
10 4
出力
370564556
サンプル3
入力
314159 265358979
出力
786063776
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。