从蓝桥杯来谈Fibonacci数列
2014年藍橋杯的第九題是這樣描述的：
? ??
? ? 給定Fibonacci數列F[]，其中，，求表達式
? ? ? ?
? ??
? ? 的值。其中
在講解這道題之前，我們先來看一個簡單版的。題目如下：
題目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1194
分析：可以看出本題就是直接求,雖然這里的很大，但是比較小啊，只到1000，那么實際上
? ? ?在Fibonacci數列中有很多有用的性質，比如：
? ? ?
? ? ?實際上，這個兩個公式的推導過程也比較簡單。（兩種證明方法：帶入公式驗證；數學歸納法）
? ??
? ? ?所以，我們可以這樣來把原表達式變形，即：
? ? ?
? ?
? ? ? 那么，我們繼續對用同樣的方法遞歸下去，容易得到：
? ? ??
? ? ? 可以看出，到了這一步，我們就把所有的Fibonacci數列的下標減小了，基本可以直接計算了。
? ? ? ? ? ? ?? ?
? ? ? 因為，所以我們得到。
? ? ? 所以到了這里，本題基本就說完了，只需要預處理前1000個Fibonacci數列即可。代碼如下：
import java.io.*; import java.util.*; import java.math.BigInteger;public class Main {final static int N = 1005;static BigInteger F[] = new BigInteger[N];static void Init(){F[0] = BigInteger.ZERO;F[1] = BigInteger.ONE;for(int i=2;i<N;i++)F[i] = F[i-1].add(F[i-2]);}public static void main(String[] args){Init();Scanner cin = new Scanner(System.in);int T = cin.nextInt();while(T-- != 0){long n = cin.nextLong();int k = cin.nextInt();int x = (int)(n % k);long y = n / k;int sign = 1;if((k & 1) == 1)sign = -1;BigInteger ans = F[x];if(sign == 1){if((y & 1L) == 1L)ans = ans.multiply(F[k-1]);}else{if((y & 1L) == 1L)ans = ans.multiply(F[k-1]);y >>= 1;if((y & 1L) == 1L) ans = ans.multiply(F[k].subtract(BigInteger.ONE));}System.out.println(ans.mod(F[k]));}} }
完美解出上題后，我們來看2014年藍橋杯的C++ A組的第九題，題目描述在文章開始處。
可以看出本題的難點在于很大，所以導致也會很大，當然求和的那部分是很簡單的。
因為，那么就有
?
所以我們可以把原問題簡單模型化為求。
?
?
經過上面簡單版題目的介紹，我們知道
?
?
又知道
?
?
那么分為奇偶情況進行討論：
?
?
一.為偶數時
??? 很明顯，這樣我們再分為奇偶進行討論
?
???（1）如果為偶數，那么有
?
???（2）如果為奇數，那么有
?
?
二.為奇數時
?
????得到，再繼續分的奇偶和的奇偶情況進行討論
?
???（1）如果為偶數且為偶數，那么
?
???（2）如果為偶數且為奇數，那么
?
?? （3）如果為奇數且為偶數，那么
?
?? （4）如果為奇數且為奇數，那么
?
?
從上面的所有情況來看，難點就在于如何進一步簡化。
?
對于這個問題，我們還有另一個性質
?
性質：若，則
?
可以看出，再對比，可知。
?
我們令，那么利用上述性質，我們替換一下：，得到：
?
，變換一下順序，即
?
，所以
?
?
可以看出，所以再分的奇偶性進行討論：
?
（1）為奇數時，
?
（2）為偶數時，
?
到了這里，我們就對進行了簡化，那么再對取余用矩陣快速冪解決即可。
?
最后，來看一道類似的題目。描述如下
題目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1365
代碼：
#include <iostream> #include <string.h> #include <stdio.h>using namespace std; typedef long long LL; const int N = 2; const int MOD = 1000000007;struct Matrix {LL m[N][N]; };Matrix I = {1, 0,0, 1 };Matrix A = {1, 1,1, 0 };Matrix multi(Matrix A, Matrix B) {Matrix C;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){C.m[i][j] = 0;for(int k = 0; k < N; k++)C.m[i][j] += A.m[i][k] * B.m[k][j];C.m[i][j] %= MOD;}}return C; }Matrix Power(Matrix A, LL n) {Matrix ans = I, P = A;while(n){if(n & 1){ans = multi(ans, P);n--;}n >>= 1;P = multi(P, P);}return ans; }//計算F(n) % MOD LL getFun(LL n) {Matrix ans = Power(A, n);return ans.m[1][0]; }//計算F(m - 1) * F(n % m) mod F(m) LL getRes(LL n, LL m) {LL k = n % m;if(k & 1)return getFun(m - k);return ((getFun(m) - getFun(m - k)) % MOD + MOD) % MOD; }LL Solve(LL n, LL m) {LL t1 = n / m;if(m & 1){LL t2 = t1 >> 1;if(t1 % 2 == 0 && t2 % 2 == 0)return getFun(n % m);if(t1 % 2 == 0 && t2 % 2 == 1)return ((getFun(m) - getFun(n % m)) % MOD + MOD) % MOD;if(t1 % 2 == 1 && t2 % 2 == 0)return getRes(n, m);if(t1 % 2 == 1 && t2 % 2 == 1)return ((getFun(m) - getRes(n, m)) % MOD + MOD) % MOD;}else{if(t1 & 1)return getRes(n, m);elsereturn getFun(n % m);} }LL getResponse(LL n, LL m) { // n += 2;LL res = Solve(n, m); // if(res == 0) // return getFun(m) - 1; // return res - 1;return res; }int main() {int T;scanf("%d", &T);while(T--){LL n, k;scanf("%lld %lld", &n, &k);printf("%lld\n", getResponse(n, k));}return 0; }
總結
以上是生活随笔為你收集整理的从蓝桥杯来谈Fibonacci数列的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 网络刷博器
- 下一篇： Fibonacci数列的幂和