hiho 113 Fibonacci

問題描述

給定一個數組，其中數子小于10000， 求fibonacci 子串的個數。

解法

容易想到如果目前數字是fibonacci數列中的一個，那麼以其結尾的fibonacci 子串個數為前一個fibonacci數字前一個的子串的個數。如果目前數字不是fibonacci 數列中的數字，則不需要考慮。

代碼

#include <bits/stdc++.h>
using namespace std;
enum{maxn = , Mod=};
int f[maxn];
int num[maxn];
int n;
int bsearch(int a)
{
    int l =, r = n;
    while(l<=r)
    {
        int m = l+(r-l)/;
        if (f[m] == a)
            return m;
        if (f[m]  < a)
            l = m+;
        else
            r = m-;
    }
    return ;
}
int main()
{
    //freopen("in.txt", "r", stdin);
    memset(num, , sizeof(num));
    f[] = f[] = ;
    for (int i=; i<maxn; ++i)
        f[i] = f[i-] + f[i-];
    scanf("%d", &n);
    for (int i=; i< n; ++i)
    {
        int a;
        scanf("%d", &a);
        if (a==)
        {
            num[] = (num[] + num[]) %Mod;
            num[] = (num[] +)%Mod;
        }
        else
        {
            int p = bsearch(a);
            if (p)
            {
                num[p] = (num[p] + num[p-])%Mod;
            }
        }
    }
    int ret =;
    for (int i=; i<maxn; ++i)
        ret = (ret + num[i])%Mod;
    printf("%d\n", ret);
    return ;
}
           

注意

1需要特殊考慮，因為fibonacci 中有兩個1；