微软2016校园招聘9月在线笔试-题目3 : Fibonacci

描述

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <Windows.h>
using namespace std;
/*
分析:
用fib记录当前最长斐波那契子序列,则有
fib[0] = 1;
fib[1] = 1;
fib[i] = fib[i-1] + fib[i-2]; (i >=2);用dp[i]记录子序列最大值为fib[i]时的子序列个数
对于vec[j]( 0<=j<=vec.size()),如果vec[j]在fib里,且索引为i,则有
dp[0] = dp[0] + 1		( i == 0);
dp[1] = dp[0] + dp[1]	( i == 0 且dp[0] != 0);
dp[i] = dp[i] + dp[i-1]	( dp[i-1] !=0 );sum = dp[0] + ... length(dp);该算法的时间复杂度为NloglogM(N为vec的长度,M为最长斐波那契子序列长度),空间复杂度为logM该算法很容易就能优化到ON的时间复杂度,我们只需要一个hash保存斐波那契数到其位置的映射即可,详细算法请参考FibSequenceEx
*/int Search(vector<int> const & vec, int val)
{auto it = lower_bound(vec.begin(), vec.end(), val);if (it == vec.end()){return -1;}return it - vec.begin();
}
int  FibSequence(vector<int> const & vec)
{int const  mod = 1000000007;vector<int> fib({ 1, 1, 2 });vector<int > dp;dp.resize(fib.size());long    sum = 0;for (auto&i : vec){if (i == 1){if (dp[0] > 0){sum = (sum + dp[0]) % mod;dp[1] = (dp[1] + dp[0]) % mod;}++dp[0];++sum;}else{int iIndex = Search(fib, i);if (iIndex != -1 && dp[iIndex - 1] != 0){int  add = dp[iIndex - 1];sum = (sum + add) % mod;dp[iIndex] = (dp[iIndex] + add) % mod;if (iIndex + 1 == fib.size()){fib.push_back(fib[iIndex] + fib[iIndex - 1]);dp.push_back(0);}}}}return sum;
}/*
通过分析我们可以知道,100000范围内的斐波那契数模59放在59大小的数组里面可以确保每个位置最多只放一个数
*/
int const hash_size = 59;
int GetIndex(vector<pair<int, int> > const & hash, int val)
{int i = val % hash_size;if (hash[i].first == val){return hash[i].second;}return -1;
}
int  FibSequenceEx(vector<int> const & vec)
{int const  mod = 1000000007;vector<int> fib({ 1, 1,2 });vector<pair<int, int> > hash;hash.resize(hash_size);hash[2] = make_pair(2, 2);vector<int > dp;dp.resize(fib.size());long    sum = 0;for (auto&i : vec){if (i == 1){if (dp[0] > 0){sum = (sum + dp[0])%mod;dp[1] = (dp[1] +  dp[0])%mod;}++dp[0];++sum;}else{int iIndex = GetIndex(hash, i);if (iIndex != -1 && dp[iIndex -1] !=0){int  add = dp[iIndex - 1];sum = (sum + add) % mod;dp[iIndex] = (dp[iIndex] + add)%mod;if (iIndex + 1 == fib.size()){int val = fib[iIndex] + fib[iIndex - 1];hash[val % hash_size] = make_pair(val, fib.size());fib.push_back(val);dp.push_back(0);}}}}	 return sum;
}void GenerateInput(vector<int> &input)
{int size = 0;cin >> size;int val = 0;for (int i = 0; i < size; ++i){cin >> val;input.push_back(val);}
}void GenerateInputEx(vector<int> &input)
{vector<int> fib({ 1, 1 });for (int i = 2; i < 100; ++i){int val = fib[i - 1] + fib[i - 2];if (val > 100000){break;}fib.push_back(val);}int n;for (n = 25; n < 100000; ++n){set<int> setF;for (size_t i = 1; i < fib.size(); ++i){if (!setF.insert(fib[i] % n).second){break;;}}if (setF.size() == fib.size()-1){break;}}int size = 0;for (size_t i = 0; i < fib.size(); ++i){for (size_t j = 0; j < 1000000 / fib.size(); ++j){input.push_back(fib[i]);}}
}
int main()
{vector<int> input;GenerateInputEx(input);DWORD t1 = ::GetTickCount();int ret1 = FibSequence(input);DWORD t2 = ::GetTickCount();int ret2 = FibSequenceEx(input);DWORD t3= ::GetTickCount();cout << ret1 << "  " << ret2 << endl;cout << t2 - t1 << " " << t3 -t2<< endl;return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;/*
通过分析我们可以知道,100000范围内的斐波那契数模59放在59大小的数组里面可以确保每个位置最多只放一个数
*/
int const hash_size = 59;
int GetIndex(vector<pair<int, int> > const & hash, int val)
{int i = val % hash_size;if (hash[i].first == val){return hash[i].second;}return -1;
}
int  FibSequenceEx(vector<int> const & vec)
{int const  mod = 1000000007;vector<int> fib({ 1, 1, 2 });vector<pair<int, int> > hash;hash.resize(hash_size);hash[2] = make_pair(2, 2);vector<int > dp;dp.resize(fib.size());long    sum = 0;for (auto&i : vec){if (i == 1){if (dp[0] > 0){sum = (sum + dp[0]) % mod;dp[1] = (dp[1] + dp[0]) % mod;}++dp[0];sum = (sum + 1) % mod;}else{int iIndex = GetIndex(hash, i);if (iIndex != -1 && dp[iIndex - 1] != 0){int  add = dp[iIndex - 1];sum = (sum + add) % mod;dp[iIndex] = (dp[iIndex] + add) % mod;if (iIndex + 1 == fib.size()){int val = fib[iIndex] + fib[iIndex - 1];if (val < 100000){hash[val % hash_size] = make_pair(val, fib.size());fib.push_back(val);dp.push_back(0);}}}}}return sum;
}int main()
{vector<int> input;int size = 0;cin >> size;int val = 0;for (int i = 0; i < size; ++i){cin >> val;input.push_back(val);}cout << FibSequenceEx(input) << endl;;return 0;
}