No.3457 Fibo-shrink
タグ : / 解いたユーザー数 76
作問者 :
くらげ
hikikomori
Problem Statement
Let $F_i$ be the Fibonacci numbers with indices starting from $0$.
That is, $F_0 = 1,\ F_1 = 1,\ F_{n+2} = F_n + F_{n+1} $.
The value of Nafmo's life is updated every 1 day.
- The value on day $0$ and earlier was $0$.
- The value on day $1$ is $S$.
- The value on the next day is the weighted sum of the values of a total of $K+1$ terms, from the current day back to $K$ days ago.
The weight for $i$ days ago $(0 \le i \le K)$ is the reciprocal of the $i$-th Fibonacci number, that is, $1 / F_i$.
You are given the value $S$ of Nafmo's life on day $1$.
Find the value of Nafmo's life on day $N$, in $\bmod\ 10007$.
$\bmod\ 10007$ of a rational number $X/Y$
Output the non-negative integer $P$ less than $10007$ satisfying $Y P \equiv X \pmod {10007}$.When $Y$ is not a multiple of $10007$, exactly one such $P$ exists for $X/Y$. Also, the value of $F_n$ is not a multiple of $10007$ in the range $1 \le n \le 10000$.
Constraints
- $1 \le K \le 500$
- $0 \le S \lt 10007$
- $1 \le N \le 10000$
- All inputs are integers.
Input
$K$ $S$ $N$
Output
With the first term $A_1$ set to $S$, output the remainder of $A_N$ divided by $10007$ on $1$ line.
$A_n$ is the sequence obtained by adding the previous $K+1$ terms, weighted by the reciprocals of the Fibonacci numbers.
Do not forget the newline at the end of the output.
Sample
Sample 1
Input
3 1 4
Output
5007
Letting $A_t$ be the value on day $t$,
$A_1 = 1$
$A_2 = \frac{A_1}{1} = 1 $
$A_3 = \frac{A_1}{1} + \frac{A_2}{1} = 2$
$A_4 = \frac{A_1}{2} + \frac{A_2}{1} + \frac{A_3}{1} = \frac{7}{2} \equiv 5007$
Therefore, since $\frac{7}{2} \equiv 5007 \mod 10007$, output `5007`.
Sample 2
Input
2 2 8
Output
5067
Letting $A_t$ be the value on day $t$,
$A_1 = 2$
$A_2 = \frac{A_1}{1} = 2 $
$A_3 = \frac{A_1}{1} + \frac{A_2}{1} = 2 + 2 = 4$
$A_4 = \frac{A_1}{2} + \frac{A_2}{1} + \frac{A_3}{1} = 1 + 2 + 4 = 7$
$A_5 = \frac{A_2}{2} + \frac{A_3}{1} + \frac{A_4}{1} = 1 + 4 + 7 = 12$
$A_6 = \frac{A_3}{2} + \frac{A_4}{1} + \frac{A_5}{1} = 2 + 7 + 12 = 21$
$A_7 = \frac{A_4}{2} + \frac{A_5}{1} + \frac{A_6}{1} = \frac{7}{2} + 12 + 21 = \frac{73}{2}$
$A_8 = \frac{A_5}{2} + \frac{A_6}{1} + \frac{A_7}{1} = 6 + 21 + \frac{73}{2} = \frac{127}{2}$
Therefore, since $\frac{127}{2} \equiv 5067 \mod 10007$, output `5067`.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。