結果

問題 No.658 テトラナッチ数列 Hard
コンテスト
ユーザー @abcde
提出日時 2019-03-30 12:40:39
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 118 ms / 2,000 ms
コード長 5,633 bytes
コンパイル時間 1,863 ms
コンパイル使用メモリ 169,236 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 18:49:50
合計ジャッジ時間 3,477 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// 参照サイト.
// 動的計画法でフィボナッチ数列の計算を速くする。
// https://yosuke-furukawa.hatenablog.com/entry/20120120/1327056359
typedef long long LL;
// const LL MOD = 1e9 + 7;
const LL MOD = 1e1 + 7;

// 行列積のロジックを一部抽出した版.
// @param p1 ～ q4: 行列の要素.
// @return ret: 行列積の計算結果.
LL matrixProduct(LL p1, LL p2, LL p3, LL p4, LL q1, LL q2, LL q3, LL q4){

    LL ret = 0;
    ret += p1 * q1, ret %= MOD;
    ret += p2 * q2, ret %= MOD;
    ret += p3 * q3, ret %= MOD;
    ret += p4 * q4, ret %= MOD;
    return ret;
}

// Tetranacci sequence の 第N項 を計算.
// A000078 Tetranacci numbers:
// https://oeis.org/A000078
// ex.
// MOD = 1e9 + 7 とすれば, 
// N = 20 なら tetranacciByMatrix(20) = 20569 % MOD      = 20569     のように計算できる.
// N = 37 なら tetranacciByMatrix(37) = 1439975216 % MOD = 439975209 のように計算できる.
// @param N: 第N項.
// @return ans: Tetranacci sequence の 第N項.
LL tetranacciByMatrix(LL N){

    // 0. N が 4以下ならば, 返却.
    if(N < 4)  return 0;
    if(N == 4) return 1;

    // 1. N を 2で割っていく.
    // ex. N = 5以降で, はじめて, 行列積を適用する必要が出てくる.
    N -= 4;
    map<LL, LL> m;
    while(N){
        LL q = N >> 1;
        LL r = N & 1;
        m[q] = r;
        N >>= 1;
    }
    // for(auto &p : m) cout << p.first << " " << p.second << endl;

    // 2. 1. の 結果から, 逆算.
    // 第 0成分(1行1列): 1, 第 1成分(1行2列): 1, 第 2成分(1行3列): 1, 第 3成分(1行4列): 1
    // 第 4成分(2行1列): 1, 第 5成分(2行2列): 0, 第 6成分(2行3列): 0, 第 7成分(2行4列): 0
    // 第 8成分(3行1列): 0, 第 9成分(3行2列): 1, 第10成分(3行3列): 0, 第11成分(3行4列): 0
    // 第12成分(4行1列): 0, 第13成分(4行2列): 0, 第14成分(4行3列): 1, 第15成分(4行4列): 0
    LL ans[16] = {1, 0, 0, 0, 
                  0, 1, 0, 0, 
                  0, 0, 1, 0, 
                  0, 0, 0, 1};
    for(auto &p : m){
        if(p.first != 0){
            LL t11 = ans[0],  t12 = ans[1],  t13 = ans[2],  t14 = ans[3],
               t21 = ans[4],  t22 = ans[5],  t23 = ans[6],  t24 = ans[7],
               t31 = ans[8],  t32 = ans[9],  t33 = ans[10], t34 = ans[11],
               t41 = ans[12], t42 = ans[13], t43 = ans[14], t44 = ans[15];
            ans[0] =  matrixProduct(t11, t12, t13, t14, t11, t21, t31, t41);
            ans[1] =  matrixProduct(t11, t12, t13, t14, t12, t22, t32, t42);
            ans[2] =  matrixProduct(t11, t12, t13, t14, t13, t23, t33, t43);
            ans[3] =  matrixProduct(t11, t12, t13, t14, t14, t24, t34, t44);
            ans[4] =  matrixProduct(t21, t22, t23, t24, t11, t21, t31, t41);
            ans[5] =  matrixProduct(t21, t22, t23, t24, t12, t22, t32, t42);
            ans[6] =  matrixProduct(t21, t22, t23, t24, t13, t23, t33, t43);
            ans[7] =  matrixProduct(t21, t22, t23, t24, t14, t24, t34, t44);
            ans[8] =  matrixProduct(t31, t32, t33, t34, t11, t21, t31, t41);
            ans[9] =  matrixProduct(t31, t32, t33, t34, t12, t22, t32, t42);
            ans[10] = matrixProduct(t31, t32, t33, t34, t13, t23, t33, t43);
            ans[11] = matrixProduct(t31, t32, t33, t34, t14, t24, t34, t44);
            ans[12] = matrixProduct(t41, t42, t43, t44, t11, t21, t31, t41);
            ans[13] = matrixProduct(t41, t42, t43, t44, t12, t22, t32, t42);
            ans[14] = matrixProduct(t41, t42, t43, t44, t13, t23, t33, t43);
            ans[15] = matrixProduct(t41, t42, t43, t44, t14, t24, t34, t44);
        }
        if(p.second == 1){
            LL t11 = ans[0],  t12 = ans[1],  t13 = ans[2],  t14 = ans[3],
               t21 = ans[4],  t22 = ans[5],  t23 = ans[6],  t24 = ans[7],
               t31 = ans[8],  t32 = ans[9],  t33 = ans[10], t34 = ans[11],
               t41 = ans[12], t42 = ans[13], t43 = ans[14], t44 = ans[15];
            ans[0] =  matrixProduct(t11, t12, t13, t14, 1, 1, 0, 0);
            ans[1] =  matrixProduct(t11, t12, t13, t14, 1, 0, 1, 0);
            ans[2] =  matrixProduct(t11, t12, t13, t14, 1, 0, 0, 1);
            ans[3] =  matrixProduct(t11, t12, t13, t14, 1, 0, 0, 0);
            ans[4] =  matrixProduct(t21, t22, t23, t24, 1, 1, 0, 0);
            ans[5] =  matrixProduct(t21, t22, t23, t24, 1, 0, 1, 0);
            ans[6] =  matrixProduct(t21, t22, t23, t24, 1, 0, 0, 1);
            ans[7] =  matrixProduct(t21, t22, t23, t24, 1, 0, 0, 0);
            ans[8] =  matrixProduct(t31, t32, t33, t34, 1, 1, 0, 0);
            ans[9] =  matrixProduct(t31, t32, t33, t34, 1, 0, 1, 0);
            ans[10] = matrixProduct(t31, t32, t33, t34, 1, 0, 0, 1);
            ans[11] = matrixProduct(t31, t32, t33, t34, 1, 0, 0, 0);
            ans[12] = matrixProduct(t41, t42, t43, t44, 1, 1, 0, 0);
            ans[13] = matrixProduct(t41, t42, t43, t44, 1, 0, 1, 0);
            ans[14] = matrixProduct(t41, t42, t43, t44, 1, 0, 0, 1);
            ans[15] = matrixProduct(t41, t42, t43, t44, 1, 0, 0, 0);
        }
    }
    
    // 3. 計算後の 第0成分(1行1列) を 返却.
    // for(int i = 0; i < 16; i++) cout << ans[i] << " ";
    return ans[0];

}

int main() {
    
    // 1. 入力情報取得.
    LL Q;
    cin >> Q;
    
    // 2. 各クエリごとに, Tetranacci数列 を 17 で割った余りを出力.
    for(LL i = 0; i < Q; i++){
        LL q;
        cin >> q;
        LL t = tetranacciByMatrix(q);
        cout << t << endl;
    }

    // 3. 後処理.
    return 0;
    
}
0