就算告诉我是矩阵快速幂我也推不出递推式呀!!!
官方题解:
对于任意i>=1,当j>=3时,有通过归纳法可以得到
进而推导出
后来自己重新推导了一遍
#include#include #include #include #include using namespace std;typedef long long ll;const ll Mod=1e9+7;const int msize=2;const int N=4;struct Mat{ ll mat[N][N];};Mat operator *(Mat a, Mat b){ Mat c; memset(c.mat, 0, sizeof(c.mat)); for(int k = 0; k < msize; ++k) for(int i = 0; i < msize; ++i) if(a.mat[i][k]) for(int j = 0; j < msize; ++j) if(b.mat[k][j]) c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod; return c;}Mat operator ^(Mat a, ll k){ Mat c; memset(c.mat,0,sizeof(c.mat)); for(int i = 0; i < msize; ++i) c.mat[i][i]=1; for(; k; k >>= 1) { if(k&1) c = c*a; a = a*a; } return c;}Mat operator -(Mat a,Mat b){ for(int i=0; i