科普网站栏目建设方案策划,北京工商注册公司,宝塔重装WordPress,肥城网站建设推广题目大意 题目链接#xff0c;给定长度为 \(n\) 的数组\(\{a_i\}\)#xff0c;问有多少个子序列是斐波那契序列$ {f_i}{1,1,2,3,5,..}$ 的前缀#xff0c;例如 \(\{1\},\{1,1,2\}\)。取值范围 $n\leq {10}^6,a_i \leq {10}^5 $。 算法思路 数组 \(a_i\) 取值在前 \(26\) 个斐… 题目大意 题目链接给定长度为 \(n\) 的数组\(\{a_i\}\)问有多少个子序列是斐波那契序列$ {f_i}{1,1,2,3,5,..}$ 的前缀例如 \(\{1\},\{1,1,2\}\)。取值范围 $n\leq {10}^6,a_i \leq {10}^5 $。 算法思路 数组 \(a_i\) 取值在前 \(26\) 个斐波那契以内可以通过递推, \(i1..n\)记录当前以 \(a_i\) 结尾的序列数量 \(r\), 设 \(a_i\) 是序列的第 \(k\) 项则 \(r_k r_k r_{k-1}\)。 举例说明 \(n5, \{a_i\} \{1,1,2,2,3\}\), 递推到 \(i5\) 时$ a_5 3 $是斐波那契第 \(4\) 项此时以 \(f_32\) 结尾的序列数为 \(2\), 那么 $r_4 r_4r_3 0 2 2 $。 最后累加 $\sum_{k1}^{26} r_k $ 即可得到结果。 需要注意的是\(f_1f_21\), 要区分开。 算法代码
#include iostream
#include map
using namespace std;const int m 26;
int f[30]; // {1,1,2,3,5,..}
mapint, int fi; // {{2,2}, {3,3}, {5,4}, {8,5}, ... }int n;
int data[1000005];
const long long int MOD 1000000007;long long int r[26] { 0 };int main()
{f[0] f[1] 1;for (int k 2; k m; k) {f[k] f[k - 1] f[k - 2];fi.insert(make_pair(f[k], k));}cin n;for (int i 1; i n; i)cin data[i];for (int i 1; i n; i) {int k 1;if (data[i] 1) {r[1] r[0];}else if (fi.find(data[i]) ! fi.end()) {k fi[data[i]];r[k] r[k - 1];r[k] % MOD;}}long long int ans 0;for (int i 0; i m; i)ans (ans r[i]) % MOD;cout ans endl;return 0;
}转载于:https://www.cnblogs.com/lessmore/p/hihocoder-1239.html
