題目大意

題目鏈接，給定長度為 \(n\) 的數(shù)組\(\{a_i\}\)，問有多少個子序列是斐波那契序列$ {f_i}={1,1,2,3,5,..}$ 的前綴，例如 \(\{1\},\{1,1,2\}\)。取值范圍 $n\leq {10}^6,a_i \leq {10}^5 $。

算法思路

數(shù)組 \(a_i\) 取值在前 \(26\) 個斐波那契以內(nèi)，可以通過遞推, \(i=1..n\)，記錄當前以 \(a_i\) 結(jié)尾的序列數(shù)量 \(r\), 設 \(a_i\) 是序列的第 \(k\) 項，則 \(r_k = r_k + r_{k-1}\)。
舉例說明， \(n=5, \{a_i\} = \{1,1,2,2,3\}\), 遞推到 \(i=5\) 時，$ a_5 = 3 $，是斐波那契第 \(4\) 項，此時以 \(f_3=2\) 結(jié)尾的序列數(shù)為 \(2\), 那么 $r_4 = r_4+r_3 = 0 +2 = 2 $。 最后累加 $\sum_{k=1}^{26} r_k $ 即可得到結(jié)果。
需要注意的是\(f_1=f_2=1\), 要區(qū)分開。

算法代碼

#include <iostream> #include <map> using namespace std;const int m = 26; int f[30]; // {1,1,2,3,5,..} map<int, 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/lessmore/p/hihocoder-1239.html

總結(jié)

以上是生活随笔為你收集整理的[递推] hihocoder 1239 Fibonacci的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。