列表

详情


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;
    }
};

上一题