给定 ,
求 F(n) % 1000000007的值
class Solution { public: /** * * @param n int整型 * @return int整型 */ const int M = 1e9+7; vector<vector<long>> D = {{1, 1, 1, 1, 1}, {0, 1, 1, 1, 1}, {0, 0, 1, 1, 1}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 0}}; vector<vector<long>> matmul(vector<vector<long>> A, vector<vector<long>> B){ int n=A.size(), m=B[0].size(), p=B.size(); vector<vector<long>> C(n, vector<long>(p)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) for(int k=0;k<p;k++) C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % M; return C; } vector<vector<long>> pow(vector<vector<long>> A, int k){ int n=A.size(); vector<vector<long>> R(n, vector<long>(n)), B=A; for(int i=0;i<n;i++) R[i][i] = 1; while(k){ if(k&1) R = matmul(R, B); B = matmul(B, B); k>>=1; } return R; } int getSum(int n) { if(n==1) return 1; if(n==2) return 4; vector<vector<long>> A=D, X(5, vector<long>(1)); X[0][0] = 4; X[1][0] = 3; X[2][0] = 2; X[3][0] = X[4][0] = 1; vector<vector<long>> T = pow(A, n-2); vector<vector<long>> R = matmul(T, X); return R[0][0]; } };
设g[j] = f[1] + f[2] + ... + f[j],h[i] = g[1] + g[2] + ... + g[i]。
因此g[j] = g[j-1] + f[j],h[i] = h[i-1] + g[i]。
那么F[n] = h[1] + h[2] + ... + h[n] = F[n-1] + h[n] = F[n-1] + h[n-1] + g[n] = F[n-1] + h[n-1] + g[n-1] + f[n] = F[n-1] + h[n-1] + g[n-1] + f[n-1] + f[n-2]。
因此我们得到递推式F[n] = F[n-1] + h[n-1] + g[n-1] + f[n-1] + f[n-2]。根据此递推式可构造矩阵相乘。
直接上矩阵快速幂即可,复杂度O(5^3logn)=O(125logn)。注意n=1和n=2时特判下即可。
#define ll long long #define mat vector<vector<ll>> const int Mod = 1e9+7; ll base[5][5] = { {1,1,1,1,1}, {0,1,1,1,1}, {0,0,1,1,1}, {0,0,0,1,1}, {0,0,0,1,0} }; class Solution { public: mat matMul(mat& a,mat& b){ int n = a.size(), m = b.size(), p = b[0].size(); mat c(n,vector(p)); for(int i=0;i<n;i++){ for(int j=0;j<p;j++){ for(int k=0;k<m;k++){ c[i][j] +=a[i][k] * b[k][j]; c[i][j]%=Mod; } } } return c; } mat pow(mat& a,int k){ int n = a.size(); mat res(n,vector(n)); for(int i=0;i<n;i++) res[i][i] = 1; mat base = a; while(k){ if(k&1) res = matMul(res,base); k>>=1; base = matMul(base,base); } return res; } /** * * @param n int整型 * @return int整型 */ int getSum(int n) { // write code here if(n==1) return 1; if(n==2) return 4; mat a(5,vector(5)); for(int i=0;i<5;i++){ for(int j=0;j<5;j++) a[i][j] = base[i][j]; } mat b(5,vector(1)); b[0][0] = 4,b[1][0] = 3, b[2][0] = 2, b[3][0] = b[4][0] = 1; mat tmp = pow(a,n-2); mat res = matMul(tmp,b); return res[0][0]; } };