小結

解決的問題：

解決遞推關系中不好直接寫出通項公式的問題，將多個遞推關系的系數在矩陣中表示

而對于矩陣的冪運算可以用快速冪，復雜度：O(m^3*logn)

所以算法核心就是找到遞推關系對應的矩陣辣

POJ 3420Quad Tiling

題意：在一個4*n的棋盤上，用1*2的多米諾骨牌來平鋪，問鋪滿的方法有多少種。

思路：這道題不能直接找到明顯的遞推關系，參考了網上一種 “ 不可分割 ” 拼湊法的概念，這樣就可以建立起遞推的關系 // 真是妙呀

當n為奇數且n>=3時，不可分割的平鋪方法為2；當n為偶數且n>=4時，不可分割的平鋪方法為3；
所以得到下列遞推式：
f(n)=f(n-1)+f(n-2)*4+f(n-3)*2+f(n-4)*3+…+f(0)*b(n)
f(n)=f(n-1)+5*f(n-2)+f(n-3)-f(n-4)

f[n-3] 0 1 0 0 f[n-4]

f[n-2] = 0 0 1 0 * f[n-3]

f[n-1] 0 0 0 1 f[n-2]

f[n] -1 1 5 1 f[n-1]

再借用矩陣的模板就ac了

#include<iostream>
#include<string.h>
using namespace std;
const int MAXN=10;
const int MAXM=10;
int r,mod;
//矩陣類模板
struct Matrix{
    int n,m;
    int a[MAXN][MAXM];
    void clear(){
        n=m=0;
        memset(a,0,sizeof(a));
    }
    Matrix operator +(const Matrix &b) const {
        Matrix tmp;
        tmp.n=n;tmp.m=m;
        for (int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                tmp.a[i][j]=a[i][j]+b.a[i][j];
        return tmp;
    }
    Matrix operator -(const Matrix &b)const{
        Matrix tmp;
        tmp.n=n;tmp.m=m;
        for (int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                tmp.a[i][j]=a[i][j]-b.a[i][j];
        return tmp;
    }
    Matrix operator * (const Matrix &b) const{
        Matrix tmp;
        tmp.clear();
        tmp.n=n;tmp.m=b.m;
        for (int i=0;i<n;++i)
            for(int j=0;j<b.m;++j)
                for (int k=0;k<m;++k){
                    tmp.a[i][j]+=a[i][k]*b.a[k][j];
                    tmp.a[i][j]%=mod;
                }
        return tmp;
    }
    Matrix get(int x){//冪運算
        Matrix E;
        E.clear();
        E.n=E.m=n;
        for(int i=0;i<n;++i)
            E.a[i][i]=1;
        if(x==0) return E;
        else if(x==1) return *this;
        Matrix tmp=get(x/2);
        tmp=tmp*tmp;
        if(x%2) tmp=tmp*(*this);
        return tmp;
    }
};
 
int main(){
 
    while(cin>>r>>mod){
        if(r==0) break;
        int a[]= {1,1,5,11};
        if(r<=3)
        {
            cout<<a[r]%mod<<endl;
            continue;
        }
        Matrix A;
        A.clear();
        A.n=A.m=4;
        A.a[0][1]=A.a[1][2]=A.a[2][3]=1;
        A.a[3][0]=-1;
        A.a[3][1]=1;
        A.a[3][2]=5;
        A.a[3][3]=1;
        A=A.get(r-3);
        Matrix M;
        M.clear();
        M.n=4;M.m=1;
        M.a[0][0]=M.a[1][0]=1;
        M.a[2][0]=5;
        M.a[3][0]=11;
        M=A*M;
        cout<<(M.a[3][0]+mod)%mod<<endl;
    }
    return 0;
}

　　

POJ 3735 Training little cats

題意：給了n,m,k分別代表有幾只貓，同樣的一套動作要做m次，這套動作有k個

有n只貓，給每只貓放食物:
g i 代表給第i只貓加一塊食物
e i 代表第i只貓吃完自己的所有食物
s i j 代表第i只貓，與第j只貓的食物互換

問這一套動作，做m次，每個貓有多少食物

思路：顯然是矩陣模板題，但是有一點就是這是一個稀疏矩陣，不能直接套用模板

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define maxn 105
int n, m, k;
struct Mat {
    ll val[maxn][maxn];
    void zero() {
        memset(val, 0, sizeof(val));
    }
    void unit() {
        zero();
        for(int i = 0; i < maxn; i++) val[i][i] = 1;
    }
}A, T;

Mat operator *(const Mat &a, const Mat &b) {
    Mat tmp;
    tmp.zero();
    for(int k = 0; k <= n; k++) {
        for(int i = 0; i <= n; i++) {
            if(a.val[i][k])
                for(int j = 0; j <= n; j++)
                    tmp.val[i][j] += a.val[i][k] * b.val[k][j];
        }
    }
    return tmp;
}

Mat operator ^(Mat x, int n) {
    Mat tmp;
    tmp.unit();
    while(n) {
        if(n & 1) tmp = tmp * x;
        x = x * x;
        n >>= 1;
    }
    return tmp;
}

void init() {
    A.zero();
    A.val[0][0] = 1;
    T.unit();
}

int main() {
    char s[5];
    int a, b;
    while(~scanf("%d%d%d", &n, &m, &k)) {
        if(!n && !m && !k) break;
        init();
        for(int i = 0; i < k; i++) {
            scanf("%s", s);
            if(s[0] == 'g') {
                scanf("%d", &a);
                T.val[0][a]++;
            } else if(s[0] == 'e') {
                scanf("%d", &a);
                for(int i = 0; i <= n; i++) T.val[i][a] = 0;
            } else {
                scanf("%d%d", &a, &b);
                for(int i = 0; i <= n; i++) swap(T.val[i][a], T.val[i][b]);
            }
        }
        Mat ans = A * (T ^ m);
        for(int i = 1; i <= n; i++) printf("%lld ", ans.val[0][i]);
        printf("
");
    }
    return 0;
}

　　

總結

以上是生活随笔為你收集整理的矩阵的幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。