快速幂（1）

链接：https://ac.nowcoder.com/acm/contest/221/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

令f(n)=2*f(n-1)+3*f(n-2)+n,f(1)=1，f[2]=2。
告诉你n，输出f(n)的结果，结果对1e9+7取模。

输入描述:

多组输入，每行一个整数n（1<=n<=1000)，如果输入为0，停止程序。

输出描述:

输出对应g(n)的值，结果对1e9+7取模。

示例1

输入

复制

输出

复制

备注:

取模即求余运算，如7%4=3，12%5=2。


这里的数据较小，直接暴力解也可以
这里是用快速幂写

以下两个代码的区别在于矩阵的乘法，左乘和右乘，他们对应的系数矩阵不一样，被乘矩阵赋的初值也不一样


B=A*B(A是系数矩阵)

#include <iostream>
#include<string.h>
#include<stdio.h>
#define ll long long
using namespace std;
const ll mod = 1000000007;
struct mat//定义矩阵结构体
{
  ll m[4][4];
  mat()
  {
    memset(m, 0, sizeof(m));
  }
};
mat mul(mat &A, mat &B)
{
  mat C;
  for (int i = 0; i < 4; i++)
  {
    for (int j = 0; j < 4; j++)
    {
      for (int k = 0; k < 4; k++) 
      {
        C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % mod;
      }
    }
  }
  return C;
}
mat pow(mat A, ll n)
{
  mat B;
  for(int i=0;i<4;i++)//初始化方阵
    B.m[i][i]=0;

  //初始被乘矩阵的初值
  B.m[0][0]=2;
  B.m[1][0]=1;
  B.m[2][0]=2;
  B.m[3][0]=1;

  while (n)
  {
    if (n & 1)
      B = mul(A, B);//注意这里，矩阵的左乘和右乘是不一样的，对应的系数矩阵也不一样
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}
int main()
{
  ll n;
  while (cin>>n&&n!=0)
  {
    mat A;//矩阵A是系数矩阵（转移矩阵）
    A.m[0][0]=2;
    A.m[0][1]=3;
    A.m[0][2]=1;
    A.m[0][3]=1;
    A.m[1][0]=1;
    A.m[2][2]=A.m[2][3]=A.m[3][3]=1;
    
    if(n==1)
    {
      printf("1
");
    }
    else if(n==2)
    {
      printf("2
");
    }
    else
    {
      mat B = pow(A, n-2);
      printf("%lld
",B.m[0][0]);
     // printf("%lld
", (2*B.m[0][0]+B.m[0][1]+2*B.m[0][2]+B.m[0][3])%mod);
    }
  }
  return 0;
}

#include <iostream>
#include<string.h>
#include<stdio.h>
#define ll long long
using namespace std;
const ll mod = 1000000007;
struct mat//定义矩阵结构体
{
  ll m[4][4];
  mat()
  {
    memset(m, 0, sizeof(m));
  }
};
mat mul(mat &A, mat &B)
{
  mat C;
  for (int i = 0; i < 4; i++)
  {
    for (int j = 0; j < 4; j++)
    {
      for (int k = 0; k < 4; k++) 
      {
        C.m[i][j] = (C.m[i][j] + A.m[i][k] * B.m[k][j]) % mod;
      }
    }
  }
  return C;
}
mat pow(mat A, ll n)
{
  mat B;
  for(int i=0;i<4;i++)
    B.m[i][i]=1;
  while (n)
  {
    if (n & 1)
      B = mul(B, A);
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}
int main()
{
  ll n;
  while (cin>>n&&n!=0)
  {
    mat A;//矩阵A是系数矩阵（转移矩阵）
    A.m[0][0]=2;
    A.m[0][1]=3;
    A.m[0][2]=1;
    A.m[0][3]=1;
    A.m[1][0]=1;
    A.m[2][2]=A.m[2][3]=A.m[3][3]=1;
    
    if(n==1)
    {
      printf("1
");
    }
    else if(n==2)
    {
      printf("2
");
    }
    else
    {
      mat B = pow(A, n-2);
      printf("%lld
", (2*B.m[0][0]+N.m[0][1]+2*B.m[0][2]+B.m[0][3])%mod);
    }
  }
  return 0;
}

应用篇

主要通过把数放到矩阵的不同位置，然后把普通递推式变成"矩阵的等比数列"，最后快速幂求解递推式:

先通过入门的题目来讲应用矩阵快速幂的套路(会这题的也可以看一下套路)：

例一:http://poj.org/problem?id=3070

题目：斐波那契数列f(n),给一个n，求f(n)%10000,n<=1e9;

(这题是可以用fibo的循环节去做的，不过这里不讲，反正是水题)

矩阵快速幂是用来求解递推式的，所以第一步先要列出递推式:

f(n)=f(n-1)+f(n-2)

第二步是建立矩阵递推式，找到转移矩阵:

,简写成T * A(n-1)=A(n)，T矩阵就是那个2*2的常数矩阵，而

这里就是个矩阵乘法等式左边:1*f(n-1)+1*f(n-2)=f(n);1*f(n-1)+0*f(n-2)=f(n-1);

这里还是说一下构建矩阵递推的大致套路,一般An与A(n-1)都是按照原始递推式来构建的，当然可以先猜一个An,主要是利用矩阵乘法凑出矩阵T,第一行一

般就是递推式，后面的行就是不需要的项就让与其的相乘系数为0。矩阵T就叫做转移矩阵(一定要是常数矩阵),它能把A(n-1)转移到A(n);然后这就是个等

比数列，直接写出通项:此处A1叫初始矩阵。所以用一下矩阵快速幂然后乘上初始矩阵就能得到An,这里An就两个元素(两个位置)，根

据自己设置的A(n)对应位置就是对应的值，按照上面矩阵快速幂写法，res[1][1]=f(n)就是我们要求的。

给一些简单的递推式

1.f(n)=a*f(n-1)+b*f(n-2)+c；（a,b,c是常数）

2.f(n)=c^n-f(n-1) ；（c是常数）

继续例题二：poj3233

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

Output

Output the elements of S modulo m in the same way as A is given

这题就是求一个矩阵的和式:S(k),直接对和式建立递推：