新兔子数列(矩阵快速幂)

简介

题目来源:2017上海大学程序设计联赛春季赛暨上海高校STEED网络赛

一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?这个问题难不倒农夫John,但当地的农夫Jack要有意为难他。刚开始时,John养了一对小兔子,Jack自第3个月起送John若干对兔子,假定第n个月送 n对兔子。兔子繁殖后形成新的兔子序列:$F_n = F_{n-1} + F_{n-2} +n,(n>1),F_1=1, F_2 =1$

给定一个整数n,求$F_n$是多少?上述问题,John自然是答不上来,现在请你帮助。

输入

多组数据,每组一行,其上有一个整数$n(0<n<=10000000000000)$。

输出

每组输出一行,输出$F_n\ (mod\ 100000007)$

样例输入

1
5

样例输出

1
20

思路

递推关系可以用以下矩阵表示
$$
\begin{pmatrix}
F_n \\
F_{n-1} \\
n \\
1
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
F_{n-1} \\
F_{n-2} \\
n-1 \\
1
\end{pmatrix}
$$
于是根据矩阵乘法的结合律可得
$$
\begin{pmatrix}
F_n \\
F_{n-1} \\
n \\
1
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{pmatrix}^{n-2}
\begin{pmatrix}
1 \\
1 \\
2 \\
1
\end{pmatrix}
$$
其中,$\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{pmatrix}^{n-2}$可以使用矩阵快速幂取模算法进行计算,将时间复杂度降低到O(log₂N)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#define MOD 100000007
#define N 4

/*----矩阵快速幂-----*/
long long tmp[N][N];
void multi(long long a[][N],long long b[][N])
{
memset(tmp,0,sizeof tmp);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
{
tmp[i][j]+=(a[i][k]%MOD*b[k][j]%MOD)%MOD;
tmp[i][j]%=MOD;
}

for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
a[i][j]=tmp[i][j];
}

long long res[N][N];
void Pow(long long a[][N],long long n)
{
memset(res,0,sizeof res);
for(int i=0;i<N;i++)
res[i][i]=1;
//单位矩阵
while(n)
{
if(n&1)
multi(res,a);
multi(a,a);
n>>=1;
}
}
/*----矩阵快速幂-----*/

int main()
{
long long n;
while (scanf("%lld",&n)==1)
{
long long tr[N][N]={{1,1,1,1},{1,0,0,0},{0,0,1,1},{0,0,0,1}};
/***********************************
F[n] 1 1 1 1 F[n-1]
F[n-1] = 1 0 0 0 * F[n]
n 0 0 1 1 n-1
1 0 0 0 1 1
***********************************/

if (n<3)
printf("1\n");
else
{
/*三天之后的递推关系使用矩阵快速幂取模计算*/
Pow(tr,n-2);
long long ans= (res[0][0]+res[0][1]+2*res[0][2]+res[0][3])%MOD;
printf("%lld\n",ans);
}
}
return 0;
}
捐助作者
0%