归纳递推数组 ,
代入初始值,求解状态矩阵 。
所以, 。
用快速幂将时间复杂度降到 。
import java.util.*; public class Main { public static final int mod = 1_000_000_007; public static long[][] multiply(long[][] matrix1, long[][] matrix2) { long[][] res = new long[matrix1.length][matrix1.length]; for (int i = 0; i < matrix1.length; i++) { for (int j = 0; j < matrix1.length; j++) { long sum = 0; for (int k = 0; k < matrix1.length; k++) sum = (sum + (matrix1[i][k] * matrix2[k][j]) % mod) % mod; res[i][j] = sum; } } return res; } public static long[][] powerN(long N, long[][] matrix) { long[][] res = new long[matrix.length][matrix.length]; for (int i = 0; i < res.length; i++) res[i][i] = 1; while (N != 0) { if ((N & 1) == 1) { res = multiply(res, matrix); } matrix = multiply(matrix, matrix); N = N >>> 1; } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); sc.close(); if (N < 1) { System.out.println(0); return; } if (N == 1 || N == 2 || N == 3) { System.out.println(N); return; } long[][] matrix = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}}; long[][] res = powerN(N - 3, matrix); System.out.println((3 * res[0][0] + 2 * res[1][0] + res[2][0]) % mod); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { static final int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); long n = Long.parseLong(br.readLine()); if(n <= 3){ System.out.println(n); }else{ long[][] base = new long[][]{{1, 1, 0}, {0, 0, 1}, {1, 0, 0}}; long[][] res = new long[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; long p = n - 3; while(p != 0){ if((p & 1) != 0) res = multiMat2D(res, base); base = multiMat2D(base, base); p >>= 1; } System.out.println((3 * res[0][0] + 2 * res[1][0] + res[2][0]) % MOD); } } private static long[][] multiMat2D(long[][] A, long[][] B) { long[][] res = new long[A.length][B[0].length]; for(int i = 0; i < res.length; i++){ for(int j = 0; j < res[0].length; j++){ long elem = 0; for(int k = 0; k < A[0].length; k++) elem = (elem + (A[i][k] * B[k][j] % MOD)) % MOD; res[i][j] = elem; } } return res; } }
#include <bits/stdc++.h> using namespace std; long long int mod = 1e9+7; #define ll long long vector<vector<ll>> matrix_mul(vector<vector<ll>>& A, vector<vector<ll>>& B) { int n = A.size(); vector<vector<ll>> C(n, vector<ll>(n, 0)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % mod) % mod; } } } return C; } vector<vector<ll>> qpow(vector<vector<ll>>& A, ll p) { int n = A.size(); vector<vector<ll>> ans(n, vector<ll>(n, 0)); for (int i = 0; i < n; i++) ans[i][i] = 1; while (p) { if (p & 0x01) { ans = matrix_mul(ans, A); } A = matrix_mul(A, A); p >>= 1; } return ans; } int main() { ll n; cin >> n; if (n <= 3) { cout << n << endl; } else { vector<vector<ll>> A = { {1, 0, 1}, {1, 0, 0}, {0, 1, 0} }; vector<vector<ll>> ans = qpow(A, n-3); cout << ((ans[0][0] * 3) % mod + (ans[0][1] * 2) % mod + ans[0][2] % mod) % mod << endl; } return 0; }
import java.util.Scanner; public class FibonacciDemo { /** * 矩阵乘法 * @param A * @param B * @return */ static long MAX = (long) (1e9 + 7); static long[][] dot(long[][] A, long[][] B) { assert (A[0].length == B.length); long tmp; long[][] R = new long[A.length][B[0].length]; for (int i = 0; i < A.length; i++) { for (int j = 0; j < B[0].length; j++) { for (int k = 0; k < A[0].length; k++) { R[i][j]+= A[i][k]* B[k][j]; } R[i][j] = (long) (R[i][j]%MAX); } } return R; } /** * 矩阵快速幂模 * @param a * @param b * @return */ public static long[][] quickMod(long[][] a, long b) { long[][] ans = new long[3][3]; b=b-3; //初始化为单位矩阵 for(int i=0;i<3 ;++i) { ans[i][i] = 1; } //计算矩阵乘法 while (b != 0) { if ((1 & b) == 1) { ans = dot(ans, a); } b >>= 1; a = dot(a , a) ; } return ans; } /** * 斐波那契通用公式: * {F(n),F(n-1),F(n-2)} = {{1, 0,1}, {1,0, 0},{0,1,0}}^(n-3) * {F(3),F(2),F(1)} * @param args */ public static void main(String[] args) { long[][] A = new long[][]{{1, 0,1}, {1, 0,0},{0, 1,0}}; long[][] B = new long[3][3]; Scanner scanner = new Scanner(System.in); long n = scanner.nextLong(); if (n > 3) { B= quickMod(A,n); long rs = (long) (3*B[0][0]+2*B[0][1]+B[0][2])%MAX; System.out.println(rs); } else { System.out.println(n); } } }
#include <cstring> using std::memcpy; using std::memset; #include <iostream> using std::ostream; using std::endl; template<typename T> /** * 矩阵类 * @tparam T 类型参数 */ class matrix { public: int row;//行 int column;//列 T **data;//数据 public: matrix(int r, int c) : row(r), column(c) { data = new T *[r]; for (int i = 0; i < r; ++i) { data[i] = new T[c]; memset(data[i], 0, column * sizeof(*data[i])); } } matrix(const matrix &m) : row(m.row), column(m.column) { data = new T *[row]; for (int i = 0; i < row; ++i) { data[i] = new T[column]; memcpy(data[i], m.data[i], column * sizeof(*data[i])); } } matrix(int r, int c, T **m) : row(r), column(c) { data = new T *[row]; for (int i = 0; i < row; ++i) { data[i] = new T[column]; memcpy(data[i], m[i], column * sizeof(*data[i])); } } matrix &operator=(const matrix &m) { if (&m == this) { return *this; } for (int i = 0; i < row; ++i) { delete[] data[i]; } delete[] data; row = m.row; column = m.column; data = new T *[row]; for (int i = 0; i < row; ++i) { data[i] = new T[column]; memcpy(data[i], m.data[i], column * sizeof(*data[i])); } return *this; } bool operator==(const matrix &m) const { if (row != m.row || column != m.column) { return false; } for (int r = 0; r < row; ++r) { for (int c = 0; c < column; ++c) { if (m[r][c] != data[r][c]) { return false; } } } return true; } inline bool operator!=(const matrix &m) const { return !operator==(m); } inline matrix operator*(const matrix &m) { return multiply(m); } inline matrix &operator*=(const matrix &m) { *this = multiply(m); return *this; } /** * 矩阵乘法 * @param m 被乘数 * @return 结果 */ matrix multiply(const matrix &m) { matrix<T> c(row, m.column); for (int i = 0; i < row; ++i) { for (int k = 0; k < m.row; ++k) { for (int j = 0; j < m.column; ++j) { c[i][j] = (c[i][j] + data[i][k] * m[k][j]); } } } return c; } /** * 矩阵乘法 * @param m 被乘数 * @param mod 结果太大的时候求mod * @return 结果 */ matrix multiply(const matrix &m, T mod) { matrix<T> c(row, m.column); for (int i = 0; i < row; ++i) { for (int k = 0; k < m.row; ++k) { for (int j = 0; j < m.column; ++j) { c[i][j] = (c[i][j] + data[i][k] * m[k][j]) % mod; } } } return c; } /** * 求矩阵m的n次幂 * 注意m.row == m.column * @param n n次幂 * @return 结果 */ matrix pow(unsigned long long n) { matrix<T> m = *this; matrix<T> res(m.row, m.row); for (int i = 0; i < m.row; ++i) { res[i][i] = 1; } while (n > 0) { if (n & (unsigned)1) { res = res.multiply(m); } m = m.multiply(m); n >>= 1; } return res; } /** * 求矩阵m的n次幂 * 注意m.row == m.column * @param n n次幂 * @param mod 结果太大的时候求mod * @return 结果 */ matrix pow(unsigned long long n, T mod) { matrix<T> m = *this; matrix<T> res(m.row, m.row); for (int i = 0; i < m.row; ++i) { res[i][i] = 1; } while (n > 0) { if (n & (unsigned)1) { res = res.multiply(m, mod); } m = m.multiply(m, mod); n >>= 1; } return res; } ~matrix() { for (int i = 0; i < row; ++i) { delete[] data[i]; } delete[] data; } T *&operator[](int r) const { return data[r]; } friend ostream &operator<<(ostream &os, const matrix &m) { os << "matrix : "; for (int i = 0; i < m.row; ++i) { if (i != 0) { os << " "; } for (int j = 0; j < m.column; ++j) { os << m[i][j] << " "; } os << endl; } return os; } }; template<typename T> T fast_fibonacci(unsigned long long n, T mod) { matrix<T> m(3, 3); m[0][0] = 1; m[0][1] = 0; m[0][2] = 1; m[1][0] = 1; m[1][1] = 0; m[1][2] = 0; m[2][0] = 0; m[2][1] = 1; m[2][2] = 0; m = m.pow(n, mod); return m[0][0] % mod; } #include <iostream> using std::cout; using std::cin; unsigned long long m = 1e9 + 7; int main(){ unsigned long long n = 0; cin >> n; cout << fast_fibonacci(n+1,m) << endl; }
#include <iostream> using namespace std; #define VAL 1000000007 typedef long long LL; int main() { LL oldcow[4] = { 0 }; LL newcow[4] = { 1 }; LL N; cin >> N; for (LL i = 0; i < N; i++) { if (i < 3) { newcow[i + 1] = 1; } else { for (LL j = 0; j < 4; j++) { oldcow[j] = newcow[j]; } newcow[0] = (oldcow[0] + oldcow[3])%VAL; newcow[1] = newcow[0]; newcow[2] = oldcow[1]; newcow[3] = oldcow[2]; } } cout << (newcow[0] + newcow[2] + newcow[3])%VAL<< endl; }为什么说我超时。。。我的时间复杂度也不大啊