Reading comprehension HDU - 4990(矩阵快速幂)

题目链接:点我

题目

---

 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\n",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

---

题意:

就是题上代码的循环里的表达式那样,让你求最后的值.

思路:

我们分析一下那个递推公式: f[n] = f[n-1] * 2 + 1 ,n 是奇数, f[n] = f[n-1] * 2 , n 是偶数,那么我们假设n是奇数,于是f[n] = f[n-1] * 2 + 1, 由于 n 是奇数, 那么n - 1 必定是偶数, 于是继续递推得到, f[n] = f[n-1] + f[n-2] * 2 + 1, 于是我们发现这个公式对于任意的 n 都成立, 那么剩下的就是构造一个矩阵, 然后快速幂就可以了.根据递推公式,构造的矩阵为:
$
\begin{pmatrix}
f[n]\
f[n-1]\
1
\end{pmatrix}
$ = $\begin{pmatrix} 1 & 2 & 1\\ 1 & 0 & 0\\ 0 & 0 & 1\\ \end{pmatrix}$ * $
\begin{pmatrix}
f[n-1]\
f[n-2]\
1 \
\end{pmatrix}
$

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;

typedef long long LL;
LL n, m;

struct mat{
    LL a[10][10];
    mat (){memset(a, 0, sizeof(a));}
    mat operator *(const mat q){
        mat c;
        for(int i = 1; i <= 3; ++i)
            for(int j = 1; j <= 3; ++j)
            if(a[i][j])
        for(int  k = 1; k  <= 3; ++k){
            c.a[i][k] += a[i][j] * q.a[j][k];
                if(c.a[i][k] >= m)
                    c.a[i][k] %= m;
        }return c;
    }
};


mat qpow(mat x, LL n){
    mat ans;
    for(int  i = 1; i <= 3; ++i)
        ans.a[i][i] = 1;
    while(n){
        if(n&1) ans = ans * x;
        x = x * x;
        n >>= 1;
    }return ans;
}


int main(){
    mat x;
    x.a[1][1] = x.a[2][1] = x.a[1][3] = x.a[3][3] = 1;
    x.a[1][2] = 2;
    while(scanf("%I64d %I64d", &n, &m) != EOF){
       mat ans =  qpow(x, n-1);
        printf("%I64d\n", (ans.a[1][1] + ans.a[1][3]) % m);
    }return 0;
}