[GXOI/GZOI2019]逼死强迫症

佚名 6年前 (2019-04-24) 随笔 1895人围观抢沙发百度已收录

题目

设我们最后的答案是\(g_n\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们发现在最后竖着放一个\(2\times 1\)的，和横着放两个\(1\times 2\)的就可以区分开之前的方案了

所以如果仅仅使用\(1\times 2\)的块来填满\(2\times n\)的格子，方案数就是\(fib_n\)

于是

\[g_n=g_{n-1}+g_{n-2}+2\sum_{i=3}fib_{n-i}\]

后面就是\(fib\)数列，就是把那两个\(1\times 1\)的在最后\(i\)列里强行区分开

于是我们矩乘就好了

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=1e9+7;
struct mat{int a[7][7];}a,s;
inline void reBuild() {
    for(re int i=0;i<7;i++)
        for(re int j=0;j<7;j++)
            a.a[i][j]=0;
    a.a[0][1]=a.a[1][0]=a.a[1][1]=1;
    a.a[2][3]=a.a[3][3]=a.a[3][2]=1;
    a.a[4][5]=a.a[5][6]=1;a.a[1][4]=2;
    a.a[6][3]=a.a[6][2]=a.a[6][6]=1;
}
inline mat operator*(mat a,mat b) {
    mat c;
    for(re int i=0;i<7;i++)
        for(re int j=0;j<7;j++)
            c.a[i][j]=0;    
    for(re int k=0;k<7;k++)
        for(re int i=0;i<7;i++)
            for(re int j=0;j<7;j++)
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
    return c;
}
inline void ksm(int b) {
    s=a;
    while(b) {if(b&1) s=s*a;b>>=1;a=a*a;}
}
int main() {
    int T=read(),x;
    while(T--) {
        reBuild();x=read();
        ksm(x);printf("%d\n",s.a[1][2]);
    }
    return 0;
}