? ? ? ? 是一道數論方面的題，融合了矩陣二分冪和多項式定理以及斐波那契數列的一道題。先用公式可以推出來，之后用矩陣二分冪就可以了。

關于矩陣二分冪，實際上就是矩陣的乘法，由于矩陣滿足結合律，故可以用平方來計算，就達到了log(n)的復雜度，由于n可能為奇數，可能為偶數，所以當n為奇數時，還需要乘以初始矩陣。

ac代碼：

#include <iostream> #include <cmath> #include <stdio.h> using namespace std; int m; int matrix[2][2];//存儲結果的矩陣 void cheng(int n){int x,y,z,w;//矩陣乘法運算x=((matrix[0][0]%m)*(matrix[0][0]%m))%m+((matrix[0][1]%m)*(matrix[1][0]%m))%m;y=((matrix[0][0]%m)*(matrix[0][1]%m))+((matrix[0][1]%m)*(matrix[1][1]%m));z=((matrix[1][0]%m)*(matrix[0][0]%m))+((matrix[1][1]%m)*(matrix[1][0]%m));w=((matrix[1][0]%m)*(matrix[0][1]%m))+((matrix[1][1]%m)*(matrix[1][1]%m));matrix[0][0]=x;matrix[0][1]=y;matrix[1][0]=z;matrix[1][1]=w;if(n%2){//乘初始矩陣x=(matrix[0][0]%m+matrix[0][1]%m)%m;y=matrix[0][0]%m;z=(matrix[1][0]%m+matrix[1][1]%m)%m;w=matrix[1][0]%m;matrix[0][0]=x;matrix[0][1]=y;matrix[1][0]=z;matrix[1][1]=w;}//取余運算matrix[0][0]%=m;matrix[0][1]%=m;matrix[1][0]%=m;matrix[1][1]%=m; } void dfs(int n){if(n==0){matrix[0][1]=0;return;}else if(n==1){matrix[0][1]=1;return;}dfs(n/2);if(n%2){//根據n的奇偶性判斷是否需要乘初始矩陣cheng(1);}elsecheng(2); } int main(){//freopen("1.txt","r",stdin);int ncase;//數據組數scanf("%d",&ncase);while(ncase--){int n;scanf("%d%d",&n,&m);matrix[0][0]=1;matrix[0][1]=1;matrix[1][0]=1;matrix[1][1]=0;n=n*2;dfs(n);//求結果printf("%d\n",matrix[0][1]%m);}return 0; }

轉載于:https://www.cnblogs.com/javaspring/archive/2012/02/15/2656408.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的杭电2855 Fibonacci Check-up的全部內容，希望文章能夠幫你解決所遇到的問題。

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