在农场中,奶牛家族是一个非常庞大的家族,对于家族中的母牛,从它出生那年算起,第三年便能成熟,成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛,它从第二年开始生小母牛。请设计一个高效算法,返回第n年的母牛总数,已知n的范围为int范围内的正整数。
给定一个正整数n,请返回第n年的母牛总数,为了防止溢出,请将结果Mod 1000000007。
测试样例:
6
返回:9
在农场中,奶牛家族是一个非常庞大的家族,对于家族中的母牛,从它出生那年算起,第三年便能成熟,成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛,它从第二年开始生小母牛。请设计一个高效算法,返回第n年的母牛总数,已知n的范围为int范围内的正整数。
给定一个正整数n,请返回第n年的母牛总数,为了防止溢出,请将结果Mod 1000000007。
6
返回:9
首先递推公式:F(n)=F(n-1)+F(n-3) 快速幂乘矩阵算法 class Cows: def countSum(self, n): res=base=[[0,0,1],[1,0,0],[0,1,1]] surplus=[[1,0,0],[0,1,0],[0,0,1]] while(n>1): if n&1: surplus=self.mutiply(surplus,res) res=self.mutiply(res,res) n=n>>1 res=self.mutiply(res, surplus) return (res[0][1]+res[1][1]+res[2][1])%1000000007 def mutiply(self,a,b):#矩阵乘法 temp=[[0,0,0],[0,0,0],[0,0,0]] for i in range(len(a)): for j in range(len(b)): for k in range(len(temp)): temp[i][j]+=a[i][k]*b[k][j]%1000000007 return temp
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; } };
//这个题目O(N)时间复杂度的做法是过不了的,测试用例是大数,只有使用O(logN)时间复杂 //度的矩阵快速幂的思路才能通过。(Cn, Cn-1, Cn-2) = (Cn-1, Cn-2, Cn-3) × {{1,1,0}, //{0,0,1},{1,0,0}} = ......= (C3, C2, C1)×{{1,1,0},{0,0,1},{1,0,0}}的n-3次幂, //注意这个矩阵{{1,1,0},{0,0,1},{1,0,0}}是可以通过解方程求出来的,9个未知数需要9个 //方程,所以多列出数列的前几项才能求出来。接下来问题就转变成了求解矩阵的n次幂问题 //了,如果n=8,我们只需要求出矩阵的4次幂就可以,要想求出4次幂,只需要求出2次幂就可以 //所以这个实际上就对应着n的二进制中等于1的进制位的数字依次相乘,结果就得到了矩阵 //的n次幂的O(logN)复杂度解法。还要提醒定义成int类型是过不了的,只有long long类型 //才能通过。涉及到大数运算,勿忘取模。 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; } };
这道题最关键的是求取matrix矩阵,以及他的基数矩阵。我们可以通过Fn=Fn-1+Fn-3了解到,通过 F1,F2,F3可以表示出任何一个Fi,(4<=i<=n).该题中,F1,F2,F3=1,2,3. 然后matrix矩阵是 等于[1,1,0],[0,0,1],[1,0,0]的,然后再做矩阵的n-3次方幂就可以求出结果。
矩阵快速幂
递推公式为D[n]=D[n-1]+D[n-3]
class Cows
{
public:
int matN = 3;
int const mod = 1e9 + 7;
typedef long long ll;
typedef vector v1;
typedef vector<vector<int>> v2;
void mul(vector>& a, vector>& b, vector>& ans)
{
for (int i = 0; i < matN; ++i)
{
for (int j = 0; j < matN; ++j)
{
ll t = 0;
for (int k = 0; k < matN; ++k)
{
t = (t + ll(a[i][k]) % mod * (b[k][j] % mod)) % mod;
}
ans[i][j] = t;
}
}
}
void fast_pow(vector>& mat, int n)
{
vector> ans(matN, vector(matN));
for (int i = 0; i < matN; ++i)
ans[i][i] = 1;
auto t = mat, tmp = ans;
while (n)
{
if (n & 1)
{
mul(ans, t, tmp);
ans = tmp;
}
n >>= 1;
mul(t, t, tmp);
t = tmp;
}
mat = ans;
}
int countSum(int n)
{
if (n <= 3) return n;
n -= 1;
int f = n % matN;
v2 mat = {{1, 1, 1}, {0, 1, 1}, {1, 1, 2}};
int c = n / 3;
fast_pow(mat, c);
int ans = 0;
ans = ((mat[0][f] % mod + 2ll * mat[1][f]) % mod + 3ll * mat[2][f]) % mod;
return ans;
}
};
import java.util.*; public class Cows { public int countSum(int n) { if(n<4) return n; long[][] res=new long[][]{{3,2,1}}; long[][] base=new long[][]{{1,1,0},{0,0,1},{1,0,0}}; n-=3; while(n>0){ if((n&1)>0){ res=multiply(res,base); } base=multiply(base,base); n=n>>1; } return (int) res[0][0]%1000000007; } public long[][] multiply(long[][] a,long[][] b){ int L1=a.length; int L2=a[0].length; int L3=b[0].length; long[][] res=new long[L1][L3]; for(int i=0;i<L1;i++) for(int j=0;j<L3;j++) for(int k=0;k<L2;k++){ res[i][j]+=a[i][k]*b[k][j]%1000000007; res[i][j]%=1000000007; } return res; } }
final static int mod = 1000000007;
public int countSum(int n) {
int f1 = 1;
int f2 = 2;
int f3 = 3;
if(n <= 4)return n;
n -= 3;
int[][] base = {{1,2,3}};
int[][] matrix ={
{0, 0, 1},
{1, 0, 0},
{0, 1, 1}
};
int[][] tmp ={
{1, 0, 0},
{0, 1, 0},
{0, 0, 1}
};
int[][] tmp1 = matrixMlu(matrix, n);
return mltHelp(base, tmp1)[0][2];
}
private int[][] matrixMlu(int[][] matrix, int n) {
if(n == 1){
return matrix;
}
if(n % 2==1){
return mltHelp(matrix, matrixMlu(matrix, n-1));
} else {
int[][] tmp = matrixMlu(matrix, n / 2);
return mltHelp(tmp, tmp);
}
}
private int[][] mltHelp(int[][] a, int[][] b) {
int[][] res = new int[3][3];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b[0].length; j++) {
for (int k = 0; k < a[i].length; k++) {
res[i][j] += (int)(((long)a[i][k] * (long)b[k][j]) % mod);
res[i][j] %= mod;
}
}
}
return res;
}
// 递推 f(n) = f(n-1)+f(n-3);
class Mad{
long[][] ad = new long[3][3];
}
public class Cows {
int mod =1000000007;
public Mad muti(Mad a,Mad b){
long temp=0;
Mad res = new Mad();
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
// if(a.ad[i][k]>mod){a.ad[i][k]=a.ad[i][k]%mod;}
// if(b.ad[k][j]>mod){b.ad[k][j]=b.ad[k][j]%mod;}
temp += (a.ad[i][k]*b.ad[k][j])%mod;
if(temp>mod){temp=temp%mod;}
}
res.ad[i][j] = temp;
temp =0;
}
}
return res;
}
public int countSum(int n){
if(n==1){return 1;}
if(n==2){return 2;}
if(n==3){return 3;}
int b = n-3;
Mad res = new Mad();
res.ad[0][0]=1;
res.ad[1][1]=1;
res.ad[2][2]=1;
Mad a = new Mad();
a.ad[0][0]=1;
a.ad[0][2]=1;
a.ad[1][0]=1;
a.ad[2][1]=1;
while(b>0){
if((b&1)==1){
res = muti(a,res);
}
b>>=1;
a = muti(a,a);
}
return (int)((3*res.ad[0][0]+2*res.ad[0][1]+res.ad[0][2])%mod);
}
}
class Cows { public: int countSum(int n) { // write code here long int f[n] ; if( n>=3 ) f[ n ] = (n-3)*(n-2)/2+3 ; else if( n==1 ) return 1 ; else if( n==2 ) return 2 ; if( n>=1000000007 ) f[n]=f[n]%1000000007 ; return f[n]; } };答案错误:您提交的程序没有通过所有的测试用例
class Cows { public: int countSum(int n) { if(n<=3) return n; long long matrix[3][3] = {{1,1,0},{0,0,1},{1,0,0}}, matrix2[3][3] = {{1,0,0},{0,0,1},{1,0,0}}, matrix3[3][3] = {{1,0,0},{0,1,0},{0,0,1}}; n = n-3; while(n!=0){ if(n&1){ for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ matrix2[i][j] = (matrix3[i][0]*matrix[0][j]+matrix3[i][1]*matrix[1][j]+matrix3[i][2]*matrix[2][j])%1000000007; } } for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ matrix3[i][j] = matrix2[i][j]; } } } for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ matrix2[i][j] = (matrix[i][0]*matrix[0][j]+matrix[i][1]*matrix[1][j]+matrix[i][2]*matrix[2][j])%1000000007; } } for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ matrix[i][j] = matrix2[i][j]; } } n = n>>1; } return (3*matrix3[0][0]+2*matrix3[1][0]+matrix3[2][0])%1000000007; } };