瓜瓜在玩着由红色和蓝色的大理石做成的玻璃珠, 他将 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 代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn = 1000005;
- const int mod = 1000000007;
- typedef long long LL;
- LL a[maxn],b[maxn];
- int main(){
- a[0]=a[1]=b[1]=1;
- for(int i=2;i<maxn;++i)
- a[i]=(a[i-1]%mod+a[i-2]%mod)%mod;// 同余
- for(int i=2;i<maxn;++i)
- b[i]=(b[i-1]+a[i])%mod;
- int n;
- while(cin>>n){
- cout<<b[n]<<endl;
- }
- return 0;
- }
ACM_无聊者序列(斐波那契数列大数 + 同余 + 规律)
来源: http://www.bubuko.com/infodetail-2607396.html