問題一覧 > 通常問題

No.1559 Next Rational

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : noya2noya2 / テスター : nok0nok0 tassei903tassei903
2 ProblemId : 6033 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-14 23:35:28

問題文

正整数 $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$ を出力してください。

制約

  • 入力はすべて整数
  • $1\le N\le 10^{18}$
  • $1\le A,B,K\le 10^9$
  • 入力

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