No.978 Fibonacci Convolution Easy
レベル :
/ AI推定難易度 : 650
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 256
作問者 :
keymoon
/ テスター :
tarattata1
タグ : / 解いたユーザー数 256
作問者 :
keymoon
/ テスター :
tarattata1
問題文最終更新日: 2020-01-30 13:22:00
English (AI translation)
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 235
(順位表)
の他の問題:
Problem Statement
Define the sequence $a$ by $a_1=0,a_2=1,a_{n}=p \cdot a_{n-1} + a_{n-2}(3 \leq n)$.
Compute $\sum_{i=1}^N\sum_{j=1}^i a_i \cdot a_j$ modulo $1000000007$.
Input
$N\ p$
- $1 \leq N \leq 2 \cdot 10^6$
- $1 \leq p \leq 10^9$
- All inputs are integers.
Output
Print $\sum_{i=1}^N\sum_{j=1}^i a_i \cdot a_j$ modulo $1000000007$. Print a newline at the end.
Sample
Sample 1
Input
3 3
Output
13
The sequence $a$ continues as $0\ 1\ 3\ 10 \cdots$. What we need to compute here is $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$, so the answer is $0 + 0 + 1 + 0 + 3 + 9 = 13$.
Sample 2
Input
10 4
Output
370564556
Sample 3
Input
314159 265358979
Output
786063776
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。