OR11. 奶牛家族
描述
在农场中,奶牛家族是一个非常庞大的家族,对于家族中的母牛,从它出生那年算起,第三年便能成熟,成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛,它从第二年开始生小母牛。请设计一个高效算法,返回第n年的母牛总数,已知n的范围为int范围内的正整数。
给定一个正整数n,请返回第n年的母牛总数,为了防止溢出,请将结果Mod 1000000007。
6
返回:9
C++ 解法, 执行用时: 1ms, 内存消耗: 384KB, 提交时间: 2017-07-28
class Cows { public: vector<vector<long long>> matrixPower(vector<vector<long long>> m, int p){ int i = 0; int row = m.size(); int col = m[0].size(); //定义单位阵 vector<vector<long long>> res(row, vector<long long>(col)); for(i = 0;i < row;i++) res[i][i] = 1; vector<vector<long long>> temp = m; while(p){ if(p & 1 == 1){ res = multiMatrix(res, temp); } temp = multiMatrix(temp, temp); p = p >> 1; } return res; } vector<vector<long long>> multiMatrix(vector<vector<long long>> A, vector<vector<long long>> B){ vector<vector<long long>> result(A.size(), vector<long long>(B[0].size())); for (int i = 0; i < result.size(); i++){ for (int j = 0; j < result[i].size(); j++){ for (int k = 0; k < A[0].size(); k++){ result[i][j] += (A[i][k] * B[k][j]) % 1000000007; result[i][j] %= 1000000007; } } } return result; } int countSum(int n) { // write code here if(n < 1) return 0; else if(n == 1 || n == 2 || n == 3) return n; vector<vector<long long>> base = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}}; vector<vector<long long>> res = matrixPower(base, n - 3); return (3 * res[0][0] + 2 * res[1][0] + res[2][0]) % 1000000007; } };
C++ 解法, 执行用时: 1ms, 内存消耗: 496KB, 提交时间: 2017-08-13
class Cows { public: int countSum(int n) { // write code here if (n == 1) return 1; long var1 = 0; long var2 = 0; long var3 = 1; n--; long a[3][3] = { {0,0,1},{1,0,0},{0,1,1} }; long rel[3][3]= { { 1,0,0 },{ 0,1,0 },{ 0,0,1 } };; while (n) { if (n % 2 == 1) matrixMul(rel, a); matrixMul(a,a); n=n/2; } return (rel[0][2]+rel[1][2]+rel[2][2]) % 1000000007; } void matrixMul(long a[3][3],long b[3][3]) { int c[3][3]; for(int i=0;i<3;i++) for (int j = 0; j < 3; j++) { long temp=0; for (int k = 0; k < 3; k++) { temp = (temp + a[i][k] * b[k][j])%1000000007; } c[i][j] = temp; } for(int i=0;i<3;i++) for (int j = 0; j < 3; j++) { a[i][j] = c[i][j]; } } };//
C++ 解法, 执行用时: 1ms, 内存消耗: 504KB, 提交时间: 2017-09-07
class Cows { const int MOD = 1000000007; vector<vector<long long>> mutip(vector<vector<long long>>& A, vector<vector<long long>>& B){//一定要是long long int L = A.size(); vector<vector<long long>> res(L, vector<long long>(L)); for(int i = 0; i < L; i++) for(int j = 0; j < L; j++) for(int k = 0; k < L; k++){ res[i][j] += ((A[i][k] % MOD) * (B[k][j] % MOD)) % MOD; } return res; } public: int countSum(int n) { if(n == 0) return 1; vector<vector<long long>> base{{0, 0, 1}, {1, 0, 0}, {0, 1, 1}}; vector<vector<long long>> res{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; n--; while(n){ if(n & 0x1) res = mutip(res, base); base = mutip(base, base); n >>= 1; } return (1 * res[0][0] + 2 * res[1][0] + 3 * res[2][0]) % MOD; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 344KB, 提交时间: 2017-07-23
class Cows { public: int countSum(int n) { if(n<=3)return n; n=n-3; long long arr[3][3]={3,2,1}; long long mul[3][3]={1,1,0,0,0,1,1,0,0}; long long temp[3][3]; while(n>0){ if((n&1)==1){ for(int i=0;i<3;i++) for(int j=0;j<3;j++) temp[i][j]=(arr[i][0]*mul[0][j]+arr[i][1]*mul[1][j]+arr[i][2]*mul[2][j])%1000000007; for(int i=0;i<3;i++) for(int j=0;j<3;j++) arr[i][j]=temp[i][j]; } for(int i=0;i<3;i++) for(int j=0;j<3;j++) temp[i][j]=(mul[i][0]*mul[0][j]+mul[i][1]*mul[1][j]+mul[i][2]*mul[2][j])%1000000007; for(int i=0;i<3;i++) for(int j=0;j<3;j++) mul[i][j]=temp[i][j]; n=n/2; } return arr[0][0]; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 352KB, 提交时间: 2017-07-19
class Cows { public: void Multiply(long a[3][3],long b[3][3]) { long res[3][3]={0}; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { for(int k=0;k<3;k++) { res[i][j]+=a[i][k]*b[k][j]%1000000007; res[i][j]%=1000000007; } } } for(int i=0;i<3;i++) { for(int j=0;j<3;j++) a[i][j]=res[i][j]; } } int countSum(int n) { if(n<4) return n; long res[3][3]={3,2,1,0,0,0,0,0,0}; long base[3][3]={1,1,0,0,0,1,1,0,0}; n-=3; while(n) { if(n%2) { Multiply(res,base); } Multiply(base,base); n/=2; } return (int)res[0][0]%1000000007; } };