class { private: typedefvector<vector<longlong>> mat;
mat Mul(mat& a, mat& b){ mat c(a.size(), vector<longlong>(b[0].size(), 0)); for(int i = 0; i < a.size(); i++) { for(int k = 0; k < a[0].size(); k++) { for(int j = 0; j < b[0].size(); j++) { c[i][j] += a[i][k] * b[k][j]; } } } return c; }
mat Pow(mat a, int n){ mat b(a.size(), vector<longlong>(a[0].size(), 0)); for(int i = 0; i < b.size(); i++) { b[i][i] = 1; } while(n) { if(n & 1) { b = Mul(b, a); } a = Mul(a, a); n >>= 1; } return b;
} public: longlongFibonacci(int n){ mat a = { {1, 1}, {1, 0} }; a = Pow(a, n); return a[1][0]; } };
近期评论