首页 > 代码库 > hihocoder#1239 Fibonacci
hihocoder#1239 Fibonacci
#1239 : 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 （微软2016年秋招第三题）
输入
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}
样例输入
62 1 1 2 2 3
样例输出
7
分析：
题意就是找到给定序列中斐波那契子序列的个数。
1. 首先想到的就是动态规划，dp[i]表示以i结尾的斐波那契子序列，然后每次变量j (0...i-1)更新i。
但是这样时间复杂度是O(n^2)，数据量10^6，肯定是超时的。
2. 考虑优化，每次更新只与斐波那契数列中的元素结尾的有关，没必要dp开那么大，并且从头遍历。
所以可以把dp存成vector<pair<int,int>>，一个表示值，一个表示以此结尾的fib序列个数。然后每次变量vector即可。
但是很遗憾，还是超时了。。。（当数组中斐波那契数列中的数存在很多时，依然是个O(n^2)）。
3. 继续优化，其实每个遍历到每个数在斐波那契序列中，更新结果时，只与其在斐波那契序列中前一个数结尾fib序列个数有关。
所以可以把dp[i]考虑存储为以fib[i]结尾的斐波那契子序列个数，100000以内斐波那契数只有25个，所以时间复杂度O(25n) = O(n)，就可以了。
注意： 用long long存result防止溢出；记得mod 1000000007
代码：
1 #include<iostream> 2 #include<unordered_map> 3 using namespace std; 4 int fib[26]; 5 const int m = 1000000007; 6 void init() { 7 int a = 1, b = 1, c = 2; 8 fib[1] = 1; 9 fib[2] = 1;10 for (int i = 3; i <= 25; ++i) {11 c = a + b;12 fib[i] = c;13 a = b;14 b = c;15 }16 }17 int findPos(int x) {18 for (int i = 1; i <= 25; ++i) {19 if (fib[i] == x) {20 return i;21 }22 }23 return -1;24 }25 26 int n;27 int nums[1000000];28 long long dp[26] = {0};29 int main() {30 init();31 cin >> n;32 long long result = 0;33 for (int i = 0; i < n; ++i) {34 cin >> nums[i];35 }36 int first = -1, second = -1;37 for (int i = 0; i < n; ++i) {38 if (nums[i] == 1) {39 first = i;40 for (int j = i + 1; j < n; ++j) {41 if (nums[j] == 1) {42 second = j;43 break;44 }45 }46 break; 47 }48 }49 if (first != -1) {50 dp[1] = 1;51 result += 1;52 }53 if (second != -1) {54 dp[2] = 1;55 dp[1] ++;56 result += 2;57 }58 if (second == -1) {59 cout << result << endl;60 return 0;61 }62 63 for (int i = second + 1; i < n; ++i) {64 if (findPos(nums[i]) == -1 ) {65 continue;66 }67 if (nums[i] == 1) { //1单独处理 68 dp[2] += dp[1];69 dp[1]++;70 result += dp[1];71 dp[2] %= m;72 result %= m;73 continue;74 }75 dp[findPos(nums[i])] += dp[findPos(nums[i]) - 1];76 result += dp[findPos(nums[i]) - 1];77 dp[findPos(nums[i])] %= m;78 result %= m;79 }80 cout << result << endl;81 }
hihocoder#1239 Fibonacci