HDU6030 Happy Necklace（推导+矩阵快速幂）

推导或者可以找规律有公式：\(f[n] = f[n-1] + f[n-3]\) 。

构造矩阵乘法：

\[\begin{pmatrix} f_i \\ f_{i-1} \\ f_{i-2} \end{pmatrix} = \begin{pmatrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}\begin{pmatrix} f_{i-1} \\ f_{i-2} \\ f_{i-3} \end{pmatrix}
\]

时间复杂度为 \(O(\log n)\) 。

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int t;

long long n;

struct Matrix{

    long long a[5][5];

};

Matrix mul(Matrix M1, Matrix M2)

{

    Matrix ret;

    memset(ret.a, 0, sizeof(ret.a));

    for(int i = 0; i < 3; i++){

        for(int j = 0; j < 3; j++){

            for(int k = 0; k < 3; k++){

                ret.a[i][j] = (M1.a[i][k] * M2.a[k][j] + ret.a[i][j]) % mod;

            }

        }

    }

    return ret;

}

void matrix_pow(long long x)

{

    Matrix ret;

    memset(ret.a, 0, sizeof(ret.a));

    for(int i = 0; i < 3; i++) ret.a[i][i] = 1;

    Matrix tmp;

    memset(tmp.a, 0, sizeof(tmp.a));

    tmp.a[0][0] = tmp.a[0][2] = tmp.a[1][0] = tmp.a[2][1] = 1;

    while(x){

        if(x & 1LL) ret = mul(ret, tmp);

        tmp = mul(tmp, tmp);

        x >>= 1LL;

    }

    long long ans = (ret.a[0][0] * 4 + ret.a[0][2] * 2 + ret.a[0][1] * 3) % mod;

    cout << ans << endl;

}

int main()

{

    for(scanf("%d", &t); t--; ){

        scanf("%lld", &n);

        if(n == 1) {puts("2"); continue;}

        else if(n == 2) {puts("3"); continue;}

        else if(n == 3) {puts("4"); continue;}

        else{

            matrix_pow(n - 3);

        }

    }

    return 0;

}

巴特西

HDU6030 Happy Necklace（推导+矩阵快速幂）

最新文章

热门文章