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 }

轉載于:https://www.cnblogs.com/acgoto/p/9058506.html

總結

以上是生活随笔為你收集整理的ACM_无聊者序列（斐波那契数列大数取余（同余）+规律）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。