时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K64bit IO Format: %lld
题目描述
现在有3个数组a,b,c
a[1]=2,a[2]=6,对所有的n>=3,a[n] = 2*a[n-1] + 3*a[n-2]。
b[1]=7,b[2]=35,对所有的n>=3,b[n] = 3*b[n-1] + 10*b[n-2]。
对所有的n>=1,有c[n] = a[n]*b[n]。
现在给你一个正整数n,返回c[n]%1000000007的值。示例1
输入
复制2
返回值
复制210
说明
a[2]=6,b[2]=35,c[2]=a[2]*b[2]=210。
示例2输入
复制10
返回值
复制207027484
链接:https://ac.nowcoder.com/acm/contest/22425/D
来源:牛客网
备注:
对于百分之20的数据:1≤n≤1e31\leq n \leq 1e31≤n≤1e3
对于百分之50的数据:1≤n≤1e71\leq n \leq 1e71≤n≤1e7
对于百分之100的数据:1≤n≤1e181\leq n \leq 1e181≤n≤1e18
请注意本题的空间限制为32MB
有点像曾经做过的一个斐波那契数列的问题,数列有递推关系,可以考虑用矩阵表示,转化为矩阵的相乘,矩阵的相乘可以用快速幂。
class Solution { public: /** * 返回c[n]%1000000007的值 * @param n long长整型 即题目中的n * @return int整型 */ int Answerforcn(long long n) { const long long mod = 1000000007; auto f = [=](std::vector<std::vector<long long>>& d, std::vector<std::vector<long long>>& e) { std::vector<std::vector<long long>> tmp = {{0, 0}, {0, 0}}; tmp[0][0] = (d[0][0] * e[0][0] + d[0][1] * e[1][0]) % mod; tmp[0][1] = (d[0][0] * e[0][1] + d[0][1] * e[1][1]) % mod; tmp[1][0] = (d[1][0] * e[0][0] + d[1][1] * e[1][0]) % mod; tmp[1][1] = (d[1][0] * e[0][1] + d[1][1] * e[1][1]) % mod; d = tmp; }; long long a1 = 2,a2 = 6; long long b1 = 7,b2 = 35; if(n == 1) return a1 * b1; if(n == 2) return a2 * b2; n -= 2; std::vector<std::vector<long long>> ma = {{2, 3}, {1, 0}}; std::vector<std::vector<long long>> mb = {{3, 10}, {1, 0}}; std::vector<std::vector<long long>> da = {{1, 0}, {0, 1}}; std::vector<std::vector<long long>> db = {{1, 0}, {0, 1}}; while(n) { if(n % 2) { f(da, ma); f(db, mb); } f(ma,ma); f(mb,mb); n /= 2; } return (((da[0][0] * a2 + da[0][1] * a1) % mod) * ((db[0][0] * b2 + db[0][1] * b1) % mod)) % mod; } };