神秘植物

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

Sample Output
3

Author
齐达拉图@HRBUST

这里先简单递推一下

序号	向上的三角形个数	向下的三角形个数
0	1	0
1	3	1
2	10	6
3	36	28

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

.	递推公式
向上的三角	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用来存储要乘的参数即如下

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