在农场中,奶牛家族是一个非常庞大的家族,对于家族中的母牛,从它出生那年算起,第三年便能成熟,成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛,它从第二年开始生小母牛。请设计一个高效算法,返回第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 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);
}
}