No.1559 Next Rational
タグ : / 解いたユーザー数 32
作問者 :
noya2
/ テスター :
nok0
tassei903
問題文
正整数 $N,A,B,K$ が与えられます。
数列 $\{a_n\}$ を次のように定めます。
$\begin{eqnarray} a_i= \begin{cases} A & ( i = 1 ) \\ B & ( i = 2 ) \\ \displaystyle\frac{{a_{i-1}}^2+K}{a_{i-2}} & (i\ge 3) \end{cases} \end{eqnarray}$
$\{a_n\}$ の第 $N$ 項 $a_N$ を求めてください。
$a_N$ は有理数になることが示せるので、これを以下に述べるように$\mod 10^9+7$ で出力してください。
有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。
ここで、$x,y$ は整数であり、$x$ は $10^9+7$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。
そして、$xz\equiv y\mod 10^9+7$ を満たすような $0$ 以上 $10^9+6$ 以下の唯一の整数 $z$ を出力してください。
制約
入力
$N\ A\ B\ K$
出力
$a_N$ を指示に従って出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 5 3 1
出力
888888897
$a_1=5,\quad a_2=3$
$\displaystyle a_{n+2}=\frac{{a_{n+1}}^2+1}{a_n}\qquad (n\ge1)$
ですから、$a_3=2,\ a_4=\frac{5}{3},\ a_5=\frac{17}{9}$ となります。
よって、$9z\equiv 17\mod 10^9+7$ となる $0$ 以上 $10^9+6$ 以下の唯一の整数 $z=888888897$ を出力します。
サンプル2
入力
100 1 2 3
出力
837764073
$a_N$ が非常に大きな値となることもあります。
サンプル3
入力
314159265358 271828 161803 57721
出力
449615573
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。