Fibonacci

Main.java

/*
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Given a sequence {an}, how many non-empty sub-sequence of it is a prefix of fibonacci sequence.

A sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

The fibonacci sequence is defined as below:

F1 = 1, F2 = 1

Fn = Fn-1 + Fn-2, n>=3

输入
One line with an integer n.

Second line with n integers, indicating the sequence {an}.

For 30% of the data, n<=10.

For 60% of the data, n<=1000.

For 100% of the data, n<=1000000, 0<=ai<=100000.

输出
One line with an integer, indicating the answer modulo 1,000,000,007.

样例提示
The 7 sub-sequences are:

{a2}

{a3}

{a2, a3}

{a2, a3, a4}

{a2, a3, a5}

{a2, a3, a4, a6}

{a2, a3, a5, a6}



样例输入
6
2 1 1 2 2 3
样例输出
7
*/

// time complexity is O(n^2), see buttom solution with O(n) time complexity
import java.util.*;
import java.math.*;

public class Main {
    private static ArrayList<Integer> fab = new ArrayList<Integer>();

    @SuppressWarnings("resource")
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            ArrayList<Integer> input = new ArrayList<Integer>();
            for (int i = 0; i < n; i++) {
                input.add(in.nextInt());
            }
            System.out.println(impl(input));
        }
    }

    public static int impl(ArrayList<Integer> input) {
        BigInteger r = BigInteger.ZERO;
        genFab(input.size());

        BigInteger[][] matrix = new BigInteger[input.size() + 1][input.size() + 1];
        for (int j = 0; j <= input.size(); j++)
            matrix[0][j] = BigInteger.ONE;

        for (int i = 1; i <= input.size(); i++) {
            for (int j = 1; j <= input.size(); j++) {
                if (fab.get(i - 1) == input.get(j - 1)) {
                    matrix[i][j] = matrix[i][j - 1].add(matrix[i - 1][j - 1]);
                } else {
                    matrix[i][j] = matrix[i][j - 1];
                }
            }
        }
        for (int i = 1; i <= input.size(); i++)
            r = r.add(matrix[i][input.size()]);

        return r.mod(new BigInteger("1000000007")).intValue();
    }

    public static void genFab(int n) {
        if (fab.size() == 0) {
            fab.add(1);
            fab.add(1);
        }
        while (fab.size() < n) {
            int s = fab.size();
            fab.add(fab.get(s - 2) + fab.get(s - 1));
        }
    }
}

// failed to notice condition of 0<=ai<=100000 at first, this can restrict fab.size() to 26, and can reduce time complexity to O(n)
// also removed usage of BigInteger, we can mod while computing
import java.util.*;

public class Main {
    private static final int MOD = 1000000007;
    private static ArrayList<Long> fab = new ArrayList<Long>();

    @SuppressWarnings("resource")
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            ArrayList<Long> input = new ArrayList<Long>();
            for (int i = 0; i < n; i++)
                input.add(in.nextLong());
            System.out.println(impl(input));
        }
    }

    public static int impl(ArrayList<Long> input) {
        int r = 0;
        genFab(26);

        int[][] matrix = new int[26][input.size() + 1];
        for (int j = 0; j <= input.size(); j++)
            matrix[0][j] = 1;

        for (int i = 1; i <= 25; i++) {
            for (int j = 1; j <= input.size(); j++) {
                matrix[i][j] = matrix[i][j - 1];
                if (fab.get(i - 1) == input.get(j - 1))
                    matrix[i][j] = (matrix[i][j] + matrix[i - 1][j - 1]) % MOD;
            }
        }

        for (int i = 1; i <= 25; i++)
            r = (r + matrix[i][input.size()]) % MOD;

        return r;
    }

    public static void genFab(int n) {
        if (fab.size() == 0) {
            fab.add(1L);
            fab.add(1L);
        }
        while (fab.size() < n) {
            int s = fab.size();
            fab.add(fab.get(s - 2) + fab.get(s - 1));
        }
    }
}