学習記録：B28 - Fibonacci Easy (mod 1000000007) , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則　演習問題集　の　B28 - Fibonacci Easy (mod 1000000007)　を解きました！いやー、余りの性質に関していい考察といいますか、トレーニングになりました。

この問題のポイント

• 余りを出すことがポイント
• nが9乗くらいあるので、フィボナッチ数列を出すことがまず困難
• でも、余りって計算するどのタイミングでとっても余りって同じになるんですよね。

参考文献

「998244353 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 , https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

目次

問題と公式解説

問題　B28 - Fibonacci Easy (mod 1000000007)

https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_ap

B28 - Fibonacci Easy (mod 1000000007) , 競技プログラミングの鉄則　演習問題集

公式解説

https://github.com/E869120/kyopro-tessoku

解答例（自作）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();

        List<Long> list = new ArrayList<Long>();
        
        long ans = 0;
        long tempTwo = 0;
        long tempOne = 0;
        long value = 1000000007;

        for (int i = 0; i < n; i++) {

            if (i == 0) {
                tempTwo = 1;
            }
            if (i == 1) {
                tempOne = 1;
            }

            ans = tempTwo + tempOne;
            ans %= value;
            tempTwo = tempOne;
            tempOne = ans;
        }

        System.out.println(ans);    
    }

}

解答例（公式をJavaに変換）

上記の例との違いは、配列を使っているか使っていないか。上記の自作解答例は配列を使わないバージョン。対して、公式のは配列を使うバージョン。どっちがいいとかじゃないとは思うけれども。公式の方がすっきりしているので、公式の方で自由自在に書けるようになりたい！

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = 1000000007;

// +9はテキトーに。まあ、溢れないようにするため。index out of.. のエラーが出ないように。
        int[] a = new int[n + 9];

// 代入
        a[1] = 1;
        a[2] = 1;

        for (int i = 3; i <= n; i++) {
// 余りを計算しちゃって格納しちゃう！
            a[i] = (a[i - 2] + a[i - 1]) % mod;
        }

        System.out.println(a[n]);
    }

}