No.720 Fibonacci Sequence Dojo with Matrices (2)
タグ : / 解いたユーザー数 59
作問者 :
hirakich1048576
/ テスター :
ixmel
Problem Statement
Define the sequence $ F_i $ as follows.
$
\begin{cases}
F_0 = 0 \\
F_1 = 1 \\
F_{i+2} = F_{i+1} + F_i
\end{cases}
$
For given integers $ N, M $, compute $ \large{ \sum_{i=1}^{n} F_{im} = \overbrace{F_m + F_{2m} + \cdots + F_{nm}}^{n} } $.
Since the answer can be very large, output it modulo $ 1000000007 $.
Input
$ N \ M $
$ 1 \leqq N \leqq 10^{10} $
$ 2 \leqq M \leqq 30000 $
Output
Output the value of $ \large{ \sum_{i=1}^{n} F_{im} = \overbrace{F_m + F_{2m} + \cdots + F_{nm}}^{n} } $ modulo $ 1000000007 $ on one line.
Sample
Sample 1
Input
4 3
Output
188
The values of $ F_1 $ through $ F_{12} $ are, in order, $ \normalsize{1, 1, \underline{\Large{2}}, 3, 5, \underline{\Large{8}}, 13, 21, \underline{\Large{34}}, 55, 89, \underline{\Large{144}}} $, so
the answer is the value of $ 2 + 8 + 34 + 144 $, which is $ 188 $.
Sample 2
Input
40964976 6561
Output
639430182
Sample 3
Input
8015993433 30000
Output
563904402
The input $ N $ may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。