問題一覧 > 通常問題

No.3457 Fibo-shrink

レベル : / AI推定難易度 : 650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 76
作問者 : t5ugu / テスター : dyktr_06 くらげ おのせ hikikomori tyawanmusi
お気に入りにしたユーザー ProblemId : 13061 / 自分の提出
問題文最終更新日: 2026-10-19 08:28:19
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
MMA Contest 021 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。