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}
样例输入
6
2 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
代码:
#include<iostream>
#include<unordered_map>
using namespace std;
int fib[];
const int m = ;
void init() {
int a = , b = , c = ;
fib[] = ;
fib[] = ;
for (int i = ; i <= ; ++i) {
c = a + b;
fib[i] = c;
a = b;
b = c;
}
}
int findPos(int x) {
for (int i = ; i <= ; ++i) {
if (fib[i] == x) {
return i;
}
}
return -;
} int n;
int nums[];
long long dp[] = {};
int main() {
init();
cin >> n;
long long result = ;
for (int i = ; i < n; ++i) {
cin >> nums[i];
}
int first = -, second = -;
for (int i = ; i < n; ++i) {
if (nums[i] == ) {
first = i;
for (int j = i + ; j < n; ++j) {
if (nums[j] == ) {
second = j;
break;
}
}
break;
}
}
if (first != -) {
dp[] = ;
result += ;
}
if (second != -) {
dp[] = ;
dp[] ++;
result += ;
}
if (second == -) {
cout << result << endl;
return ;
} for (int i = second + ; i < n; ++i) {
if (findPos(nums[i]) == - ) {
continue;
}
if (nums[i] == ) { //1单独处理
dp[] += dp[];
dp[]++;
result += dp[];
dp[] %= m;
result %= m;
continue;
}
dp[findPos(nums[i])] += dp[findPos(nums[i]) - ];
result += dp[findPos(nums[i]) - ];
dp[findPos(nums[i])] %= m;
result %= m;
}
cout << result << endl;
}
最新文章
- 转 10 个最佳的 Node.js 的 MVC 框架
- Express 4 handlebars 不使用layout写法
- 关于delphi 中 Sender的学习
- C 语言中包含的标准头文件(24个)
- LINQ to PostgreSQL Tutorial
- hdu 2156
- 定制ToolChain for ARM
- 九章lintcode作业题
- Cookie的简单使用
- Linq分组,linq方法分组
- Prim和Kruskal最小生成树
- Xshell无法连接到LINUX虚拟机
- 【java学习】spring mvc 公共dao的实现,定义基本的增删改查
- hibernate--hibernate.cfg.xml常用配置详解
- Windows的GDI映射方式,逻辑坐标,设备坐标的理解
- iOS-野指针与僵尸对象
- 再论sklearn分类器
- keras系列︱迁移学习:利用InceptionV3进行fine-tuning及预测、完美案例(五)
- Thinkphp5模板继承
- 【转】器件为什么只听英文Datasheet的话
热门文章
- sublime中用less实现css预编译
- JavaScript中this的指向2(转载)
- js 百度地图和谷歌地图的选择
- dll加载过程全局变量会先初始化
- Slackware网卡配置文件和配置工具
- 2019阿里云开年Hi购季域名与商标分会场全攻略!
- ML面试1000题系列(51-60)
- python3.7的celery报错TypeError: wrap_socket() got an unexpected keyword argument &#39;_context&#39;
- 开启php中短标签<;%%>;和<;??>;的方法
- 二.使用JDBC对数据库CRUD