题目3 : Fibonacci
2024-09-07 15:35:38
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
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
// Java版本
import java.awt.im.InputContext;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner; public class Main {
/* 2
0 0
0 3 1.000 1.000 5.000 */
static HashSet<Integer> fibSet=new HashSet<Integer>();
static HashMap<Integer, Integer> fibMap=new HashMap<Integer, Integer>();
static HashMap<Integer, Integer> fibMap2=new HashMap<Integer, Integer>();
public static void fib(){
fibMap.put(1, (int) 1);
fibMap.put(2, (int) 1);
fibSet.add((int) 1);
fibMap2.put((int) 1, 1);
for(int i=3; i<50; i++){ fibMap.put(i, fibMap.get(i-1)+fibMap.get(i-2));
fibMap2.put(fibMap.get(i-1)+fibMap.get(i-2), i);
fibSet.add(fibMap.get(i-1)+fibMap.get(i-2));
}
//System.out.println("fibmap"); }
//如果有a之前的所有
public static boolean hasPre(int a, HashMap<Integer, Integer> nums){
int k=fibMap2.get(a); boolean result=true;
for(int i=k-1;i>2; i--){ if(nums.get(fibMap.get(i)) !=null &&nums.get(fibMap.get(i)) >0){
continue;
}else{
result=false;
break;
}
} if(result&& nums.get(1)!=null &&nums.get(1)>1 ){
result= true;
}else{
result= false;
} return result; } public static int precount(int a, HashMap<Integer, Integer> nums){
long count=1;
int k=fibMap2.get(a); for(int i=k-1;i>2; i--){
count=count*nums.get(fibMap.get(i)); }
count*=(nums.get(1)*(nums.get(1)-1)/2);
return (int) (count%1000000007); }
public static void main(String[] args) { Scanner scanner = new Scanner(System.in);
int n=scanner.nextInt();
int a[] = new int[n];
for(int i=0; i<n; i++){
a[i]=scanner.nextInt(); }
fib();
//fib计数
HashMap<Integer, Integer> nums=new HashMap<Integer, Integer>();
boolean has1=false;
long count=0;
for(int i=0; i<n; ++i){
//如果等于1,那就好弄
//System.out.println(a[i]+""+fibSet.contains((long)a[i]) );
if(a[i]==1){
if(nums.containsKey(1)){
count=count+nums.get(1)+1;
nums.put(1, nums.get(1)+1); }else{
nums.put(1, 1);
count+=1;
}
has1=true; }else if(has1&& nums.get(1)>1&& fibSet.contains(a[i]) && hasPre(a[i],nums)){ count=(count+precount(a[i],nums))%1000000007;
if(nums.containsKey(a[i])){
nums.put(a[i], nums.get(a[i])+1);
}else{
nums.put(a[i], 1);
} }
//System.out.println(nums);
} System.out.println(count);
scanner.close();
} }
最新文章
- Struts2中的ModelDriven机制及其运用
- linux 安装mysql两种方式
- Postman-进阶
- PDA手持移动POS销售开单软件(网络版)、PDA手持设备小票机
- 初试visual studio2012的新型数据库LocalDB
- Android获取系统cpu信息,内存,版本,电量等信息
- 深入研究B树索引(一)
- linq 总结
- Mybatis学习笔记(一) 之框架原理
- Java操作*.properties
- memcached添加IP白名单,只允许指定服务器调用
- SoapUI:入门实例
- JMeter打开脚本失败 如何解决?
- vmware虚拟机磁盘挂载
- 02.Control
- JDK环境安装步骤
- 1.golang的环境搭建及入门
- 前端开发周报: CSS 布局方式方式与JavaScript数据结构和算法
- BZOJ.1901.Dynamic Rankings(线段树套平衡树 Splay)
- Javascript中点击(click)事件的3种写法