HDU 1757 A Simple Math Problem 矩阵快速幂

题意：给你一个序列，0 - 9 项已经知道了分别等于下标，现在给你一个公式 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);

要你求 f[m] % k, 其中m < 2^31。

解题思路：矩阵快速幂。转移矩阵如下图。其实利用矩阵快速幂的重点和难点就是构造出转移矩阵

盗图，google图片没有找到来源。

这个图的意思是把 F[9] 变为 F[10] ，然后把1-8都往下移位，消除 F0 ,进行 n-9次左乘这个转置矩阵以后，就可以得出我们想要的解了，又因为有结合律，我们可以先对这个转移矩阵快速幂以后再求解。

解题代码：

快速幂的代码是参考了kuangbin的部分代码。

  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 
 26 using namespace std;
 27 int k , m; 
 28 struct Matrix
 29 {
 30    LL mat[10][10];
 31    void clear()
 32    {
 33       memset(mat,0,sizeof(mat));
 34    }
 35    void output()
 36    {
 37      for(int i =0  ;i < 10 ;i ++)
 38      {
 39        for(int j = 0 ;j < 10 ;j ++)
 40            printf("%I64d ",mat[i][j]);
 41      printf("
");
 42      }
 43    }
 44    void init()
 45    {
 46       for(int i = 0;i < 10 ;i ++) 
 47           for(int j = 0 ;j < 10;j ++)
 48           {
 49               if(i == j + 1 ) mat[i][j] = 1;
 50           }
 51    }
 52    Matrix operator *(const Matrix &b) const
 53    {
 54        Matrix ret;
 55        ret.clear();
 56        for(int i = 0 ;i < 10 ;i ++)
 57            for(int j = 0;j < 10;j ++)
 58            {
 59                for(int k = 0 ;k < 10 ;k ++)
 60                {
 61                  ret.mat[i][j] =(ret.mat[i][j] + mat[i][k] * b.mat[k][j]) % m ; // 第I 行  第J  列        
 62                }
 63            }
 64        return ret;
 65    }
 66 };
 67 Matrix Pow( Matrix a, int n)
 68 {
 69   Matrix ret;
 70   ret.clear();
 71   for(int i = 0 ;i <= 9 ;i ++)
 72        ret.mat[i][i] = 1;
 73   Matrix tmp = a; 
 74   while(n)
 75   {
 76       if(n&1) ret = ret * tmp;
 77       tmp = tmp * tmp;
 78       n >>=1;
 79   }
 80   return ret;
 81 }
 82 int main(){
 83     while(scanf("%d %d",&k,&m) != EOF)
 84     {
 85          Matrix  a;
 86          a.clear();
 87          for(int i =0 ;i < 10 ;i ++)
 88          {
 89              scanf("%I64d",&a.mat[0][i]);
 90          }
 91          a.init();
 92          //a.output();
 93          if(k <= 9 )
 94          {
 95             printf("%d
",k % m );
 96             continue;
 97          }
 98          a = Pow(a,k-9);
 99          //a.output();
100          LL ans = 0 ;
101          for(int i = 0 ;i <= 9;i ++)
102          {
103             ans =(ans + (9-i) * a.mat[0][i]) % m ;
104          }
105       printf("%I64d
",ans);
106     }
107 return 0;
108 }

View Code

没有梦想，何谈远方