覺得還是有必要發日志的……否則就在題海中迷失了自己的腳步咯

題目如標題，下面是程序……不要問我矩陣是怎么想的……

1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdlib> 5 #include <queue> 6 #include <stack> 7 #include <vector> 8 #include <iostream> 9 #include "algorithm" 10 using namespace std; 11 typedef long long LL; 12 const int MAX=5; 13 LL a,n,p; 14 struct Mat{ 15 LL x,y; 16 LL mat[MAX][MAX]; 17 Mat (){ 18 x=y=0; 19 memset(mat,0,sizeof(mat)); 20 } 21 Mat operator * (const Mat &cc) { 22 int i,j,k; 23 Mat zt; 24 zt.x=x,zt.y=cc.y; 25 for (i=1;i<=zt.x;i++) 26 for (j=1;j<=cc.y;j++) 27 for (k=1;k<=cc.x;k++) 28 zt.mat[i][j]=(zt.mat[i][j]+mat[i][k]*cc.mat[k][j])%p; 29 return zt; 30 } 31 }m1,m2; 32 void init(){ 33 int i,j; 34 scanf("%lld%lld%lld",&a,&n,&p); 35 m1.x=2,m1.y=1; 36 m1.mat[1][1]=m1.mat[2][1]=a; 37 m2.x=2,m2.y=2; 38 m2.mat[1][1]=10,m2.mat[1][2]=1; 39 m2.mat[2][1]=0,m2.mat[2][2]=1; 40 } 41 Mat ksm(Mat zt,LL k){ 42 Mat an; 43 LL i,j; 44 an.x=zt.x,an.y=zt.y; 45 for (i=1;i<=an.x;i++) 46 for (j=1;j<=an.y;j++) 47 an.mat[i][j]=(i==j); 48 while (k) 49 {if (k%2==1) 50 an=an*zt; 51 zt=zt*zt; 52 k/=2; 53 } 54 return an; 55 } 56 int main(){ 57 freopen ("ksm.in","r",stdin); 58 freopen ("ksm.out","w",stdout); 59 int i,j; 60 init(); 61 m1=ksm(m2,n-1)*m1; 62 printf("%lld",m1.mat[1][1]); 63 return 0; 64 }

?

轉載于:https://www.cnblogs.com/keximeiruguo/p/5947265.html

總結

以上是生活随笔為你收集整理的aaaaaaa……aaa(n个)%p的值 (矩阵快速幂)的全部內容，希望文章能夠幫你解決所遇到的問題。

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