矩阵加速数列递推

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4973

ZOJ Problem Set - 3690 

#include <iostream>
#include <cstring>
using namespace std;

struct Matrix{ 
#define MAXN 2 
#define MOD 1000000007
 
int  x,y; 
long long  b[MAXN][MAXN]; 
 
struct CannotMultiply{}; 
 
Matrix(){ 
    x=y=0; 
    memset(b,0, sizeof(b)); 
  } 
 
Matrix operator*(const  Matrix& t)const { 
    if(y!=t.x)throw  CannotMultiply(); 
    Matrix r;r. x=x;r. y=t. y; 
    for (int  i=0;i<x;++i){ 
      for (int  j=0;j<t.y;++j){ 
        for (int  k=0;k<y;++k){ 
          r. b[i][j]+= b[i][k]*t.b[k][j]; 
          r. b[i][j]%=MOD; 
        } 
      } 
    } 
    return r; 
  } 
 
#undef MOD 
#undef MAXN 
}; 
int main()
{
    //A[i]=(m-k)*ALL[i-1]
    //ALL[i-1]=(m-1)(All[i-1])+A[i-1]
    //0 m-k A[i]
    //1 m-1 F[i]
    //A[1]=(m-k) F[1]
    int n,m,k;
    while(cin>>n>>m>>k){
        Matrix A,t;
        t.x=t.y=A.x=A.y=2;
        A.b[0][0]=A.b[1][1]=t.b[1][0]=1;
        t.b[0][1]=m-k;
        t.b[1][1]=m-1;
        for(;n>0;n>>=1,t=t*t)
            if(n&1)A=A*t;
        cout<<(A.b[1][0]+A.b[1][1])%1000000007<<endl;            
    }
    return 0;
}

poj 3734 Blocks

f[i][a][b]（a,b=0/1）表示长度为i的序列，红绿颜色的奇偶情况分别为a,b。递推公式比较好写，答案就是f[n][0][0]，后两维也可以用一个两位二进制数表示。可以发现F[0]={1,1,1,1}，所以写起来也比较简洁。其实实现上不需要体现出状态，全是矩阵乘。

#include <iostream>
#include <cstring>
using namespace std;

struct Matrix{

#define MAXN 4
#define MOD 10007

int  x,y;
long long  data[MAXN][MAXN];

struct CannotMultiply{};

Matrix(int _x=0,int _y=0):x(_x),y(_y){
    memset(data,0, sizeof(data));
  }
Matrix operator*(const  Matrix& rig)const {
    if(y!=rig.x)throw  CannotMultiply();
    Matrix res;
    res.x=x;
    res.y=rig.y;
    for (int  i=0;i<x;++i){
      for (int  j=0;j<rig.y;++j){
        for (int  k=0;k<y;++k){
          res.data[i][j] += data[i][k]*rig.data[k][j];
          res.data[i][j] %= MOD;
        }
      }
    }
    return res;
  }

};

Matrix pow(Matrix A,int n){
    Matrix res(A.x,A.y);
    for(int i=0;i<res.x;i++) res.data[i][i]=1;
    for(;n>0;n>>=1,A=A*A)
        if(n&1)
            res=res*A;
    return res;
}

int main()
{
    Matrix f(4,4);
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            f.data[i][j]=1;
    for(int i=0;i<4;i++){
        f.data[i][i]  =2;
        f.data[i][3-i]=0;
    }

    int T;cin>>T;
    while(T--){
        int n;
        cin>>n;
        Matrix ans;
        ans=pow(f,n);
        cout<<ans.data[0][0]<<endl;
    }
    return 0;
}