斐波那契数列问题的递归和动态规划3

斐波那契数列问题的递归和动态规划3

题目描述

假设农场中成熟的母牛每年只会生 1 头小母牛，并且永远不会死。第一年农场中有一只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 n，求出 n 年后牛的数量。

输入描述：

输入一个整数 n。

输出描述：

输出 n 年后牛的数量对 1e9 + 7 取模的值。

示例1

输入

6

输出

9

备注：

$1\le n\le 10^{18}$

---

题解：

递推公式： $F(n)=F(n-1)+F(n-3)$ ，是一个三阶递推数列，矩阵乘法表示形式为： $$\left[\begin{array}{ccc}F(n)& F(n-1)& F(n-2\end{array}\right]=\left[\begin{array}{ccc}F(n-1)& F(n-2)& F(n-3)\end{array}\right]\times \left[\begin{array}{ccc}1& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]$$

$$...$$

$$\left[\begin{array}{ccc}F(n)& F(n-1)& F(n-2\end{array}\right]=\left[\begin{array}{ccc}F(3)& F(2)& F(1)\end{array}\right]\times {\left[\begin{array}{ccc}1& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]}^{n-3}$$

代码：

#include <cstdio> #include <cstring> using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; LL n; LL tmp[3][3]; void mat_mul(LL ret[][3], LL ans[][3]) { memset(tmp, 0LL, sizeof tmp); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { for (int k = 0; k < 3; ++k) { tmp[i][j] += ret[i][k] * ans[k][j] % MOD; tmp[i][j] %= MOD; } } } memcpy(ret, tmp, sizeof tmp); } void solve(LL n) { LL ret[][3] = {{1,0,0},{0,1,0},{0,0,1}}; LL ans[][3] = {{1,1,0},{0,0,1},{1,0,0}}; while (n) { if (n & 1LL) mat_mul(ret, ans); mat_mul(ans, ans); n >>= 1LL; } printf("%lld\n", (3 * ret[0][0] + 2 * ret[1][0] + ret[2][0]) % MOD); } int main(void) { scanf("%lld", &n); if (n < 4LL) return 0 * printf("%lld\n", n); solve(n - 3LL); return 0; }