矩阵题目

本文从WordPress迁移而来, 查看全部WordPress迁移文章

hdu 3306 Another kind of Fibonacci

转化一下公式吧

构造一个矩阵 （ si-1，Ai^2 , Ai-1 ^ 2） ， 得到 (si , Ai+1 ^ 2 , Ai^2)

Ai + 1 = X Ai + Y Ai - 1 , Ai + 1^2 = X^2 Ai^2 + Y^2 Ai^2 + 2 X Y Ai Ai - 1

多了 Ai * Ai-1 这个项，所以就往矩阵里面加点东西吧…

（ si-1，Ai^2 , Ai-1 ^ 2 ， Ai Ai-1） ——> (si , Ai+1 ^ 2 , Ai^2 , Ai+1 Ai)

看看Ai+1 Ai , Ai+1 Ai = (X Ai + Y Ai-1) Ai = X Ai^2 + Y Ai Ai-1

这样就有Ai*Ai-1了

构造矩阵
1  0   0  0
1 X^2  1  X
0 Y^2  0  0
0 2XY  0  Y

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define MOD 10007
#define MAXSIZE 4

class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef long long elemtype;
    int row,col;
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}

    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            a[i][j] = 1;
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                for(int k = 0; k < col; k++)
                    now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
        return now;
    }

    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++)
                printf("%d ",a[i][j]);
            puts("");
        }
    }
};

matrix A,M,B;

int main(){
   A.reset(1,4);
   M.reset(4,4);
   A.a[0][0] = 1; A.a[0][1] = 1; A.a[0][2] = 1; A.a[0][3] = 1;
   LL n,x,y;
   while(cin >> n >> x >> y){
      M.a[0][0] = 1; M.a[0][1] = 0; M.a[0][2] = 0; M.a[0][3] = 0;
      M.a[1][0] = 1; M.a[1][1] = (x*x)%MOD; M.a[1][2] = 1; M.a[1][3] = x%MOD;
      M.a[2][0] = 0; M.a[2][1] = (y*y)%MOD; M.a[2][2] = 0; M.a[2][3] = 0;
      M.a[3][0] = 0; M.a[3][1] = (2*x*y)%MOD; M.a[3][2] = 0; M.a[3][3] = y%MOD;

      if(n == 0) puts("0");
      else{
         B = (A * (M ^ (n-1)));
         cout << (B.a[0][0]+B.a[0][1])%MOD << endl;
      }
   }
   return 0;
}

hdu 1588 Gauss Fibonacci

这题的话，挺好的，其实有之前两道矩阵题的结合

fibs矩阵(简称A)

1 1
1 0

它的幂次就是对应的fibs项

所以f(g(i))统一用fibs矩阵表示

f(g0) = f(b) = A^b
f(g1) = f(k+b) = A ^ (k+b)
f(g2) = f(2k+b) = A ^ (2k+b)
......
f(gn-1) = f(k(n-1)+b) = A ^ (k(n-1)+b)

求和，那么首先把A^b提出来，剩下A^k + A^2k + A^3K …………………

把A^k单独看为B，变为B + B^2 + B^3 + B^4 + ……………….

这就变成了 poj 3233 Matrix Power Series 可以两种方法做

另外，考虑一下b = 0，k = 0的话，会怎样？

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define LL long long
#define MAXSIZE 4
 
LL MOD;

class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef LL elemtype; 
    int row,col;         
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}
   
    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){ 
    for(int i = 0; i < row; i++) 
        for(int j = 0; j < col; j++) 
            a[i][j] = 1; 
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }
   
    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                for(int k = 0; k < col; k++)
                    now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
        return now;
    }
   
    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++)
                printf("%d ",a[i][j]);
            puts("");
        }
    }
};

matrix A,B,Ab,L,MID,R;

void solve(LL k,LL b,LL n){
    B = (A ^ (int)k);
    //B.show();
    L.reset(2,4);
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++){
            L.a[i][j] = 0LL;
            L.a[i][j+2] = B.a[i][j];
        }
    MID.reset(4,4);
    for(int i = 0 ; i < 2; i++)
        for(int j = 0; j < 2; j++){
            MID.a[i][j] = i == j ? 1LL : 0LL;
            MID.a[i+2][j] = i == j ? 1LL : 0LL;
            MID.a[i][j+2] = 0;
            MID.a[i+2][j+2] = B.a[i][j];
        }
    //(MID ^ (n-1)).show();
    R = L * (MID ^ (n-1));
    //R.show();
    matrix unit(2,2);
    unit.identity();
    R = R + unit;
}

int main(){
    LL k,b,n;
    while(cin >> k >> b >> n >> MOD){
        A.reset(2,2);
        A.a[0][0] = 1LL; A.a[0][1] = 1LL;
        A.a[1][0] = 1LL; A.a[1][1] = 0LL;
        if(b == 0LL){
            if(k == 0LL) puts("0");
            else{
                // B = A^k
                // A^k + A^2k + A^3k ..... + A^(n-1)k
                // B + B^2 + B^3 + ...... + B^(n-1)
                solve(k,b,n);
                cout << R.a[0][1] << endl;
            }
        }
        else{
            Ab = (A ^ (int)b);
            if(k == 0LL){ cout << (A.a[0][1]*n)%MOD << endl; }
            else{
                // B = A^k
                // A^b * (I + B + B^2 + B^3 .... + B^(n-1))
                solve(k,b,n);
                R = R * Ab;
                cout << R.a[0][1] << endl;
            }
        }
    }
    return 0;
}