No.3457 Fibo-shrink
タグ : / 解いたユーザー数 60
作問者 :
t5ugu
/ テスター :
dyktr_06
くらげ
おのせ
hikikomori
tyawanmusi
問題文
$F_i$ を、添え字が $0$ から始まるフィボナッチ数とします。
つまり、$F_0 = 1,\ F_1 = 1,\ F_{n+2} = F_n + F_{n+1} $ です。
Nafmo 君の人生の価値は、1日ごとに更新されます。
- $0$ 日目以前の価値は $0$ でした
- $1$ 日目の価値は $S$ です
- 次の日の価値は、現在 および $K$ 日前までの、合計 $K+1$ 項の価値の重みつきの総和で表されます。
$i$ 日前 $(0 \le i \le K)$ に対する重みは、$i$ 番目のフィボナッチ数の逆数、つまり $1 / F_i$ です。
$1$ 日目の Nafmo 君の人生の価値 $S$ が与えられます。
$N$ 日目における Nafmo 君の人生の価値を、$\bmod\ 10007$ で求めてください。
有理数 $X/Y$ の $\bmod\ 10007$
$Y P \equiv X \pmod {10007}$ をみたす、$10007$ 未満の非負整数 $P$ を出力してください。$X/Y$ に対してただひとつ存在します。制約
- $1 \le K \le 500$
- $1 \le S \lt 10007$
- $1 \le N \le 10000$
- 入力はすべて整数
入力
$K$ $S$ $N$
出力
初項 $A_1$ を $S$ とした場合の $A_N$ を $10007$ で割った余りを $1$ 行で出力してください。
$A_n$ は、直前の $K+1$ 項をフィボナッチ数の逆数で重みづけして足した数列です。
出力の末尾の改行を忘れないようにしてください。
サンプル
サンプル1
入力
3 1 4
出力
5007
$t$ 日目における価値を $A_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$
よって、$\frac{7}{2} \equiv 5007 \mod 10007$ より、`5007` を出力します。
サンプル2
入力
2 2 8
出力
5067
$t$ 日目における価値を $A_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}$
よって、$\frac{127}{2} \equiv 5067 \mod 10007$ より、`5067` を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。