Codeforces #257 div.2 B

概要

http://codeforces.com/contest/450/problem/B
昨日に引き続き。
なかなか楽しい問題でした。
今回はScalaっぽいこともできます。

問題

超シンプル。
以下の数式がある。
$f_n$の値を$10^9+7$で剰余を取り出力せよ。

f_1 = x; f_2 = y;\forall i (i \leq 2), f_i = f_{i-1} + f_{i+1}

1 \leq n \leq 10^9

アルゴリズム

式変形

まずは、馬鹿正直に与えられた数式を使ってみます。
早速サンプル１、$x=2,y=3,n=3$の時を考えましょう。
数式に当てはめて・・・

f_3 = f_2 + f_4 \\
 = 3 + f_4 \\
 = ...

$f_4$ が出ちゃったのォ！？ ﾀﾞﾚｶﾀｽｹﾃｰ

というわけで、式変形しましょう。

(1) f_i = f_{i-1} + f_{i+1} \\
(2) f_{i+1} = f_i - f_{i-1} \\
(3) f_i = f_{i-1} - f_{i-2}

(3)を使うと、

f_1 = x \\
f_2 = y \\
f_3 = f_2 - f_1 = y - x \\
f_4 = f_3 - f_2 = (y-x) - y = -x

やったね！どこまでも行ける！

速度的に

どこまでも行けるようになったのはいいですが…。
nが$10^9$とデカイので、O(n)でも死にそう。
O(logn)とかO(1)にしないと競プロ的にはアウト。

O(n)でもダメということは、フィボナッチとかでよくあるメモ化してもダメ。
冪乗でフィボナッチ数を求めるような、画期的な何かが必要ですね。

式変形アゲイン

というわけで、再度式を眺めてみます。
こういう時は、しばらく項を求めてみると何かが見えるもんです。
実際にしばらく求めてみましょう。

f_5 = f_4 - f_3 = -x - (y-x) = y \\
f_6 = f_5 - f_4 = y - (-x) = y + x \\
f_7 = f_6 - f_5 = (y+x) - y = x \\
f_8 = f_7 - f_6 = x - (y+x) = y \\
f_9 = f_8 - f_7 = y - x

$f_7$が・・・。
$f_1$に帰っちゃったのォ！？ﾀﾞﾚｶﾀｽ(ry

不思議ですが、この性質を使えばnがいくら大きかろうか、$f_1$～$f_6$のどれかを使えばOK。
O(1)で求められます。

剰余

言語によって、以下のコードの結果が異なります。

-1 % 10

これが9になるか、-1になるかは言語それぞれですが、Scalaでは-1のままです。困った。

しょうがないので、以下のテクニックを使って、Mで剰余を取った時負数にならないようにします。

( ( -1 % M ) + M ) % M

解答

今回はJava的な書き方とScala的な書き方を分けてみます。

Java的記述

6要素を持つ配列を用意して、そこに入れます。
念のため、Int - Intをする時にも剰余を取っておきます。

import scala.math.BigInt

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val x, y, n = sc.nextInt

  def solve( x: Int, y: Int, n: Int ): Int = {
    val M: Int = 1e9.toInt + 7

    val newN = (n-1) % 6

    var memo = new Array[Int](6)
    memo(0) = x
    memo(1) = y
    for( i <- (2 until 6) ) {
      memo(i) = ( memo(i-1) - memo(i-2) ) % M
    }

    ( ( memo(newN) % M ) + M ) % M
  }

  println( solve( x, y, n ) )
}

分かりやすいですね。
これで通ります。

Scala的記述

関数型言語的には、無限リストを作ってn番目の要素を取り出すのが美しい気がします。
ついでにBigIntを使って、Int - Intをしても大丈夫なようにしておきます（BigIntの計算速度わからんけど）。

import scala.math.BigInt

object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val x, y, n = sc.nextInt

  def solve2( x: Int, y: Int, n: Int ): Int = {
    val M: Int = 1e9.toInt + 7

    val newN = (n-1) % 6

    def tail(a: BigInt, b: BigInt): Stream[BigInt] = a #:: tail(b, b - a)
    val res = tail(x, y)(newN)
    ( ( ( res % M ) + M ) mod M ).toInt
  }

  println( solve( x, y, n ) )
}

なんとなく、エレガント。

結果

Time: 233ms
Memory: 0 KB