Luogu

BZOJ

LOJ

分析

设 $f[i]$ 为 $2\times i$ 的答案, $g[i]$ 为斐波那契数列的第 $i$ 项( $g[0]=g[1]=1$ ), $h[i]$ 为 $\sum\limits_{j=1}^i g[i]$ 。

那么有 $f[i]=f[i-1]+f[i-2]+2h[i-3]$ 。

至于怎么得到的,戳这里咕咕咕

因为 $h[i]=g[i+2]-1$ ,所以上式化为 $f[i]=f[i-1]+f[i-2]+2g[i-1]-2$ 。

矩阵快速幂优化一波即可。大概是$\begin{bmatrix}f_{i-2}&f_{i-1}&g_{i-2}&g_{i-1}&2\end{bmatrix}\times\begin{bmatrix}0&1&0&0&0\\1&1&0&0&0\\0&0&0&1&0\\0&2&1&1&0\\0&-1&0&0&1\end{bmatrix}=\begin{bmatrix}f_{i-1}&f_{i}&g_{i-1}&g_i&2\end{bmatrix}$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;

struct Matrix {
    int n,m;
    int s[10][10];

    Matrix() { n=m=0; memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} A,G;

Matrix operator *(Matrix a,Matrix b) {
    Matrix c; c.n=a.n,c.m=a.m;
    for (re int i=1;i<=c.n;++i)
        for (re int j=1;j<=c.m;++j)
            for (re int k=1;k<=a.m;++k)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}

inline Matrix qpow(Matrix a,int b) {
    Matrix c; c.n=a.n,c.m=a.m;
    for (re int i=1;i<=c.n;++i) c[i][i]=1;
    for (;b;b>>=1,a=a*a)
        if (b&1) c=c*a;
    return c;
}

int main() {
    G.n=G.m=5;
    G[1][2]=G[2][1]=G[2][2]=G[3][4]=G[4][3]=G[4][4]=G[5][5]=1;
    G[4][2]=2,G[5][2]=mod-1;
    int T=read();
    while (T--) {
        int n=read();
        if (n<3) { puts("0"); continue; }
        A.n=1,A.m=5;
        A[1][1]=0,A[1][2]=0,A[1][3]=1,A[1][4]=2,A[1][5]=2;
        A=A*qpow(G,n-2);
        printf("%d\n",A[1][2]);
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 21 PM