[原创]hrbust 1430 神秘植物 [递推+矩阵快速幂]

2016-03-14 17:44:24 Tabris_ 阅读数:426


博客爬取于2020-06-14 22:44:47
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50888426


题目链接

神秘植物

Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 49(25 users) Total Accepted: 23(19 users) Rating: Special Judge: No
Description
Leyni有一种神秘的植物,形状是一种“向上”三角形植物,每过一年,每个“向上”三角形植物会变成三个“向上”三角形植物和一个“向下”三角形植物,每个“向下”三角形植物会变成三个“向下”三角形植物和一个“向上”三角形植物。如下图:

1 2 3

Leyni想知道经过n年有多少个“向上”三角形植物。

Input
输入包含多组测试数据。

对于每组测试数据:

第1行,包含一个整数n (0 ≤ n ≤ 10^18)

处理到文件结束

Output
对于每组测试数据:

第1行,输出Leyni拥有多少个“向上”三角形植物。(MOD 1000000007)

Sample Input
1

2

Sample Output
3

10

Author
齐达拉图@HRBUST


这里先简单递推一下

序号向上的三角形个数向下的三角形个数
010
131
2106
33628

不难观察出规律 ,规律如下

.递推公式
向上的三角shang[i]=3*shang[i-1]+xia[i-1]
向下的三角xia[i]=3*xia[i-1]+shang[i-1];

虽然观察出了本题的规律了
但是! 但是!! 但是!!!
观察input 题目说
n (0 ≤ n ≤ 10^18)
n (0 ≤ n ≤ 10^18)
n (0 ≤ n ≤ 10^18)

10^18次幂 先不说超时 光是数组也开不出来啊

怎么办呢 ??
仔细想想 用两个二维数组相乘的话 一个表示要乘的参数 一个用来存数据就能开出来了
数组如下

1
long long int a[2][2],c[2][2];

其中a用来存储数据 ,c用来存储要乘的参数 即如下

1
2
3
4
5
a[0][0]=1; a[0][1]=0;
a[1][0]=0; a[1][1]=0;

c[0][0]=3; c[0][1]=1;
c[1][0]=1; c[1][1]=3;

这样下来用矩阵的乘法就能求了

上述已经解决了 内存爆的情况 但是 时间上怎么优化呢
既然是矩阵 那自然可以用矩阵快速幂来优化 这样下来时间可是几何倍数的被优化

不懂矩阵快速幂的可以看这里 矩阵快速幂

时间 空间的优化都结束了 就可以A题了 ~~


附本题代码

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
# include<stdio.h>
int m=1000000007;
void mul(long long int a[2][2], long long int b[2][2])
{
long long int c[2][2];
int i, j, k;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]=(c[i][j]+a[i][k]*b[k][j])%m;
}
}
}
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
b[i][j]=c[i][j];
}
}
}
long long int a[2][2], e[2][2];
void init()
{
e[0][0]=3; e[0][1]=1;
e[1][0]=1; e[1][1]=3;

a[0][0]=1; a[0][1]=0;
a[1][0]=0; a[1][1]=0;
}
void solve(long long int n)
{
init();
//n=n-1;
while (n > 0)
{
if (n%2==1)
{
mul(e, a);
}
mul(e, e);
n = n >> 1;
}
printf("%lld\n", a[0][0]);
}
int main()
{
long long int n;
while(~scanf("%lld", &n))
{
solve(n);
}
return 0;
}