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

Tabris

CSDNhrbust

发布于：2016年3月14日

次浏览

[原创]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有一种神秘的植物，形状是一种“向上”三角形植物，每过一年，每个“向上”三角形植物会变成三个“向上”三角形植物和一个“向下”三角形植物，每个“向下”三角形植物会变成三个“向下”三角形植物和一个“向上”三角形植物。如下图：

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

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

对于每组测试数据：

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

处理到文件结束

Output
对于每组测试数据：

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

Sample Input
1

2

Sample Output
3

10

Author
齐达拉图@HRBUST

这里先简单递推一下
| 序号|向上的三角形个数|向下的三角形个数|
|:--|:--|:--|
|0|1|0|
|1|3|1|
|2|10|6|
|3|36|28|

不难观察出规律 ，规律如下
|.|递推公式|
|--|:-----|
|向上的三角|shang[i]=3shang[i-1]+xia[i-1]|
|向下的三角|xia[i]=3xia[i-1]+shang[i-1];|

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

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

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

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

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

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题了 ~~

附本题代码

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

本页文档最后更新于：2021年5月4日

CSDN

递推

矩阵快速幂

hrbust1430