【筆記】矩陣快速冪

  • 【用途】將矩陣視為一個物件,用快速冪的思想進行運算。
    • constructor mat():宣告 mat 物件時,順便將矩陣的元素初始值設為 0。
    • mat operator * (const mat &b) const; 多載 (overloading) 乘法運算子*
    • mod:此處定義為全域變數。
  • 【練習】ZeroJudge a451: 10229 – Modular Fibonacci【題解
  • 【練習】ZeroJudge d828: Pascal’s triangle’s secret (II)【題解
  • 【練習】ZeroJudge b062: 1. 城市道路連通網【題解
  • 【練習】TIOJ 2053 . 費氏數列(Fibonacci)【題解
struct mat{
    int a[2][2];

    mat(){
        //constructor
        memset(a, 0, sizeof(a));
    }

    mat operator * (const mat &b) const{
        mat ret;
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 2; j++){
                for (int k = 0; k < 2; k++){
                    ret.a[i][j] = (ret.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return ret;
    }
};
分享本文 Share with friends