首页 > 代码库 > FZU 1683 纪念SlingShot 矩阵快速幂

FZU 1683 纪念SlingShot 矩阵快速幂

2024-07-23 01:39:12   214人阅读

题意：中文不说了

解题思路：矩阵快速幂求和。我们可以知道我们可以用矩阵快速幂求他的F[n],显然，每多出一个F[n] 我们就要把它加入到我们的和里面，但是 因为我们是快速幂，不能求出所有的f[n]，所以我们只能多加一维矩阵来维护和。

中间矩阵

3 2 7 0

1 0 0 0

0 1 0 0

1 0 0  1（和）

初始矩阵

5

3

1

4 （前两项的和）

解题代码：

  1 // File Name: temp.cpp  2 // Author: darkdream  3 // Created Time: 2014年09月17日 星期三 11时35分45秒  4   5 #include<vector>  6 #include<list>  7 #include<map>  8 #include<set>  9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define m 2009 26 using namespace std; 27 int n ;  28 struct Matrix 29 { 30    int  mat[4][4]; 31    void clear() 32    { 33       memset(mat,0,sizeof(mat)); 34    } 35    void output() 36    { 37      for(int i =0  ;i < n ;i ++) 38      { 39        for(int j = 0 ;j < n ;j ++) 40            printf("%d ",mat[i][j]); 41      printf("\n"); 42      } 43    } 44    void init() 45    { 46       clear(); 47       n = 4 ; 48       mat[0][0] = 3;  49       mat[0][1] = 2;  50       mat[0][2] = 7; 51       mat[1][0] = 1; 52       mat[2][1] = 1; 53       mat[3][0] = 1; 54       mat[3][3] = 1; 55    } 56    Matrix operator *(const Matrix &b) const 57    { 58        Matrix ret; 59        ret.clear(); 60        for(int i = 0 ;i < n ;i ++) 61            for(int j = 0;j < n;j ++) 62            { 63                for(int k = 0 ;k < n ;k ++) 64                { 65                  ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行  第J  列         66                } 67            } 68        return ret; 69    } 70 }; 71 Matrix Pow( Matrix a ,LL t ) 72 { 73   Matrix ret; 74   ret.clear(); 75   for(int i = 0 ;i < n ;i ++) 76        ret.mat[i][i] = 1; 77   Matrix tmp = a;  78   while(t) 79   { 80       if(t&1) ret = ret * tmp; 81       tmp = tmp * tmp; 82       t >>=1; 83   } 84   return ret; 85 } 86 int main(){ 87     int l ; 88     int ca = 0 ; 89     int t ; 90     scanf("%d",&t); 91     while(t--) 92     { 93         ca ++; 94         scanf("%d",&l); 95         int tt[] = {4,1,3,5}; 96         if(l <= 2) 97         { 98           if(l == 0 ) 99            printf("Case %d: 1\n",ca);100           if(l == 1 )101            printf("Case %d: 4\n",ca);102           if(l == 2 )103            printf("Case %d: 9\n",ca);104            continue;105         }106         Matrix  a;107         a.init();108         a = Pow(a,l - 1);109         //a.output();110         int ans = 0 ; 111         for(int i = 0 ;i < n;i ++)112         {113            ans = (ans + a.mat[3][i] *tt[3-i] )%m ;114         }115         printf("Case %d: %d\n",ca,ans);116     }117     return 0;118 }
View Code

 

FZU 1683 纪念SlingShot 矩阵快速幂


联系
我们