题目3 : Fibonacci

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

时间限制: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

样例输出

EmacsNormalVim

// Java版本

import java.awt.im.InputContext;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Scanner;

public class Main {

/*

2

0 0

0 3

1.000 1.000 5.000

 */

    static HashSet<Integer> fibSet=new HashSet<Integer>();

    static    HashMap<Integer, Integer>  fibMap=new HashMap<Integer, Integer>();

    static    HashMap<Integer, Integer>  fibMap2=new HashMap<Integer, Integer>();

    public static void fib(){

        fibMap.put(1, (int) 1);

        fibMap.put(2, (int) 1);

        fibSet.add((int) 1);

        fibMap2.put((int) 1, 1);

        for(int i=3; i<50; i++){

            fibMap.put(i, fibMap.get(i-1)+fibMap.get(i-2));

            fibMap2.put(fibMap.get(i-1)+fibMap.get(i-2), i);

            fibSet.add(fibMap.get(i-1)+fibMap.get(i-2));

        }

        //System.out.println("fibmap");

    }

    //如果有a之前的所有

    public  static boolean hasPre(int a, HashMap<Integer, Integer> nums){

        int k=fibMap2.get(a);

        boolean result=true;

        for(int i=k-1;i>2; i--){

            if(nums.get(fibMap.get(i)) !=null  &&nums.get(fibMap.get(i)) >0){

                continue;

            }else{

                result=false;

                break;

            }

        }

        if(result&& nums.get(1)!=null &&nums.get(1)>1 ){

            result= true;

        }else{

            result= false;

        }

        return result;

    }

    public static int precount(int a, HashMap<Integer, Integer> nums){

        long count=1;

        int k=fibMap2.get(a);

        for(int i=k-1;i>2; i--){

            count=count*nums.get(fibMap.get(i));

        }

        count*=(nums.get(1)*(nums.get(1)-1)/2);

        return (int) (count%1000000007);

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n=scanner.nextInt();

        int a[] = new int[n];

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

            a[i]=scanner.nextInt();

        }

        fib();

        //fib计数

        HashMap<Integer, Integer>  nums=new HashMap<Integer, Integer>();

        boolean has1=false;

        long count=0;

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

            //如果等于1,那就好弄

            //System.out.println(a[i]+""+fibSet.contains((long)a[i]) );

            if(a[i]==1){

                if(nums.containsKey(1)){

                    count=count+nums.get(1)+1;

                    nums.put(1, nums.get(1)+1);

                }else{

                    nums.put(1, 1);

                    count+=1;

                }

                has1=true;

            }else if(has1&& nums.get(1)>1&& fibSet.contains(a[i]) && hasPre(a[i],nums)){

                count=(count+precount(a[i],nums))%1000000007;

                if(nums.containsKey(a[i])){

                    nums.put(a[i], nums.get(a[i])+1);

                }else{

                    nums.put(a[i],  1);

                }

            }

            //System.out.println(nums);

        }

        System.out.println(count);

        scanner.close();

    }

}