首页 > 其他 > 详细

ACM_无聊者序列(斐波那契数列大数+同余+规律)

时间:2018-05-19 01:07:32      阅读:337      评论:0      收藏:0      [点我收藏+]

Problem Description:

瓜瓜在玩着由红色和蓝色的大理石做成的玻璃珠,他将n个玻璃珠从左到右排成一个序列叫做无聊者序列。一个非空的红色和蓝色玻璃珠组成的序列是一个无聊者序列。这个序列的玻璃珠颜色是交替的,例如:序列(红色;蓝色;红色)和(蓝色)是一个无聊者序列。(红色;红色)不是无聊者序列。现在,瓜瓜想知道,从这个序列中选出一个无聊者子序列有多少种方法。并将它mod(1000000007)。

Input:

输入有多组数据,输入一个整数n(1 <= n <= 10^6),代表这个无聊者序列的个数。

Output:

输出一个数,代表子序列的个数为多少,该数需要mod(1000000007)

Sample Input:

3
4

Sample Output:

6
11
Hint:
对于第一个样例,假如我们猜测瓜瓜初始排列的玻璃珠序列为(红色;蓝色;红色),那么无聊者序列的子序列将会是以下6个:
红
蓝
红
红蓝
蓝红
红蓝红
解题思路:规律题。简单推导一下前5个玻璃珠构成地无聊者序列:记红色为0,蓝色为1;规则:序列颜色是交替的。
当n=1时,假设序列是0(当然也可以是1,但只要其中地一种情况就可以了),所以子序列为0--->1个;
当n=2时,假设序列是01(当然也可以是10),此时的子序列为0、1、01--->3个;(1+2
当n=3时,假设序列是010(当然也可以是101),此时的子序列为0、1、0、01、10、010--->6个;(3+3
当n=4时,假设序列是0101(当然也可以是1010),此时的子序列为0、1、0、1、01、01、10、01、010、101、0101--->11个;(6+5
当n=5时,假设序列是01010(当然也可以是10101),此时的子序列为0、1、0、1、0、01、01、10、10、01、10、010、010、010、101、010、0101、1010、01010--->19个;(11+8
以上求子序列要按照无聊者序列规则来从左到右推导,通过观察结果个数之间的关系,可以发现后一个数减去前一个数的结果刚好为斐波那契数列规律,于是果断打表,但打表过程可能出现数据过大,此时的取余应为同余思想,剩下就简单了,水过。
AC代码:
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000005;
 4 const int mod = 1000000007;
 5 typedef long long LL;
 6 LL a[maxn],b[maxn];
 7 int main(){
 8     a[0]=a[1]=b[1]=1;
 9     for(int i=2;i<maxn;++i)
10 a[i]=(a[i-1]%mod+a[i-2]%mod)%mod;//同余 11 for(int i=2;i<maxn;++i) 12 b[i]=(b[i-1]+a[i])%mod; 13 int n; 14 while(cin>>n){ 15 cout<<b[n]<<endl; 16 } 17 return 0; 18 }

ACM_无聊者序列(斐波那契数列大数+同余+规律)

原文:https://www.cnblogs.com/acgoto/p/9058506.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!