題目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5237

題意：給定和，其中，，求??的值。

分析：嗯，這道題貌似有難度，如果比較小的話我們可以構造矩陣，實際上這樣做也挺麻煩的。

?????以前我們做一個大Fibonacci數列模一個大素數都是用矩陣，當然這里素數滿足條件：5是模這個素數的二

???? 次剩余，那么現在要求不要用矩陣來計算這個結果呢？那就是今天我要討論的問題，本題也是基于這種思路。

?

?????本題我們可以直接利用Fibonacci數列的公式進行計算。因為我們知道Fibonacci數列的公式為：

? ? ??

? ? ?雖然公式中含有根號，但是我們知道是一個整數，而且5是模1000000009的二次剩余。那么可以通過逆元

? ? ?和二次剩余的轉化來做。比如就可以用中的來代替。

? ? ?為了方便表示，我們令：

? ? ?

? ? ?那么得到

? ? ?

? ? ?把按照二項式展開得到

? ? ?

? ? ?對于每一個都這樣表示，那么相同的合并后是等比數列，比如對于所有系數為合并后為

? ? ?， 其中

? ? ?所以到了這里本題就明確了，枚舉每一個從0到，依次計算即可。

? ? ?當然對于，我們可以階乘預處理然后求逆元，至于和同樣預處理，這樣時間少很多。

? ? ?可以看出本題條件好在1000000009是素數，而且5是模1000000009的二次剩余。

? ? ?經計算2模1000000009的逆元是500000005，而的一個解為383008016。

? ? ?也就是說對于有

? ? ?

? ? ??

? ? ?同理，對于有

? ? ?

? ? ?嗯，貌似還有一個問題沒有處理，t = 1時咋辦？ 這個很簡單啦，不用等比求和公式即可。其實吧，這里面

? ? ?我們還可以注意到，也可以進一步優化，讀者自己體會，就說到這里。

代碼：

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; typedef long long LL; const int N = 100005; const LL MOD = 1000000009;LL fac[N],A[N],B[N];void Init() {fac[0] = 1;for(int i=1; i<N; i++)fac[i] = fac[i-1] * i % MOD;A[0] = B[0] = 1;for(int i=1; i<N; i++){A[i] = A[i-1] * 691504013 % MOD;B[i] = B[i-1] * 308495997 % MOD;} }LL quick_mod(LL a,LL b,LL MOD) {LL ans = 1;a %= MOD;while(b){if(b & 1){ans = ans * a % MOD;b--;}b >>= 1;a = a * a % MOD;}return ans; }LL Solve(LL n,LL k) {LL ans = 0;for(int r=0; r<=k; r++){LL t = A[k-r] * B[r] % MOD;LL x = fac[k];LL y = fac[k-r] * fac[r] % MOD;LL c = x * quick_mod(y,MOD-2,MOD) % MOD;LL tmp = t * (quick_mod(t,n,MOD) - 1) % MOD * quick_mod(t-1,MOD-2,MOD) % MOD;if(t == 1) tmp = n % MOD;tmp = tmp * c % MOD;if(r & 1) ans -= tmp;else ans += tmp;ans %= MOD;}LL m = quick_mod(383008016,MOD-2,MOD);ans = ans * quick_mod(m,k,MOD) % MOD;ans = (ans % MOD + MOD) % MOD;return ans; }int main() {int T;LL n,k;Init();scanf("%d",&T);while(T--){cin>>n>>k;cout<<Solve(n,k)<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Fibonacci数列的幂和的全部內容，希望文章能夠幫你解決所遇到的問題。

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