問題一覧 > 通常問題

No.1559 Next Rational

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 23
作問者 : noya2 / テスター : nok0 tassei903
お気に入りにしたユーザー ProblemId : 6033 / 自分の提出
問題文最終更新日: 2021-06-14 23:35:28
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
yukicoder contest 301 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,A,B,K$.

Define the sequence $\{a_n\}$ as follows.

$\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}$

Find the $N$-th term $a_N$ of $\{a_n\}$.

It can be shown that $a_N$ is a rational number, so output it $\mod 10^9+7$ as described below.


To output a rational number, first represent it as a fraction $\frac{y}{x}$.

Here, $x,y$ are integers, and $x$ must not be divisible by $10^9+7$ (under the constraints of this problem, such a representation is always possible).

Then, output the unique integer $z$ between $0$ and $10^9+6$, inclusive, such that $xz\equiv y\mod 10^9+7$.

Constraints

  • All inputs are integers.
  • $1\le N\le 10^{18}$
  • $1\le A,B,K\le 10^9$

    • Input

    $N\ A\ B\ K$

    Output

    Output $a_N$ as instructed.

    Print a newline at the end.

    Sample

    Sample 1
    Input
    5 5 3 1
    Output
    888888897

    $a_1=5,\quad a_2=3$

    $\displaystyle a_{n+2}=\frac{{a_{n+1}}^2+1}{a_n}\qquad (n\ge1)$

    Therefore, $a_3=2,\ a_4=\frac{5}{3},\ a_5=\frac{17}{9}$.

    Thus, output the unique integer $z=888888897$ between $0$ and $10^9+6$, inclusive, such that $9z\equiv 17\mod 10^9+7$.

    Sample 2
    Input
    100 1 2 3
    Output
    837764073

    $a_N$ can be a very large value.

    Sample 3
    Input
    314159265358 271828 161803 57721
    Output
    449615573

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。