HDU 4990 Reading comprehension 简单矩阵快速幂

Problem Description

Read the program below carefully then answer the question.
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include<iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include<vector>

const int MAX=100000*2;
const int INF=1e9;

int main()
{
  int n,m,ans,i;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    ans=0;
    for(i=1;i<=n;i++)
    {
      if(i&1)ans=(ans*2+1)%m;
      else ans=ans*2%m;
    }
    printf("%d ",ans);
  }
  return 0;
}

Input

Multi test cases，each line will contain two integers n and m. Process to end of file.
[Technical Specification]
1<=n, m <= 1000000000

Output

For each case，output an integer，represents the output of above program.

Sample Input

1 10 3 100

Sample Output

1 5

题意：给出了原程序，显然，看到内涵的递推式明显可以使用矩阵快速幂了。

思路：原递推式是当n为偶数时fn=2*f(n-1)+1 奇数时fn=2*f(n-1) 找规律得到递推式为 f(n) = 1*f(n-1)+2*f(n-2) +1*1

（下面是没学过线代的鶸的一点理解）

其实可以把矩阵看做一个储存多数据的容器，例如这题

运算为等式右红框分别乘以左边三个红框得到的三个值

对应的就是等式左侧的f(n),f(n-1),1。

化简

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <string.h>
 5 #define ll __int64
 6 using namespace std;
 7 
 8 ll mod;
 9 struct matrix
10 {
11     ll x[3][3];
12     void init()
13     {
14         for(int i = 0; i < 3; i++)
15             for(int j = 0; j < 3; j++)
16                     x[i][j] = 0;
17     }
18 };
19 
20 matrix mul(matrix a, matrix b)
21 {
22     matrix c;
23     c.init();
24     for( int i = 0; i < 3; i++)
25         for(int j = 0; j < 3; j++)
26         {
27             for(int k = 0; k < 3; k++)
28             {
29                 c.x[i][j] += a.x[i][k] * b.x[k][j];
30             }
31             c.x[i][j] %= mod;
32         }
33     return c;
34 }
35 matrix powe(matrix x, ll n)
36 {
37     matrix r;
38     r.init();
39     r.x[1][1] = r.x[0][0] = r.x[2][2] = 1; //初始化
40 
41     while(n)
42     {
43         if(n & 1)
44             r = mul(r , x);
45         x = mul(x , x);
46         n >>= 1;
47     }
48     return r;
49 }
50 int main()
51 {
52 
53     ll x, y, n, ans;
54     //while(~scanf("%I64d%I64d", &n, &mod))
55     while(cin >> n >> mod)
56     {
57         if(n == 2)
58             printf("%I64d
", 2%mod);
59         else if(n == 1)
60             printf("%I64d
", 1%mod);
61         else
62         {
63             matrix d;
64             d.init();
65             d.x[0][0] = 1;
66             d.x[0][1] = 1;
67             d.x[1][0] = 2;
68             d.x[2][0] = 1;
69             d.x[2][2] = 1;
70 
71             d = powe(d, n - 2);
72 
73             ans = d.x[0][0] * 2 + d.x[1][0] * 2 + 1; //如果使用手动乘，不知为何还要再判断
74 
75             matrix e;
76             e.init();
77             e.x[0][0] = 2;
78             e.x[0][1] = 1;
79             e.x[0][2] = 1;
80             d = mul(e , d);
81             /*if( n % 2 ) //再判断
82                 ans-=2;
83             else
84                 ans-=1;*/
85             cout << d.x[0][0] % mod << endl;
86         }
87     }
88 }