游客 注册 | 登录
中文 | En

3052 - 找规律系列之：三角形中的三角形

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

还记得当初我出的圆中的三角形那道题么？是不是感觉比较难，我感觉也是，所以为了补偿大家所以出一道很水的找规律题让大家来秒了它。如下图，第一个是第0年，第二个是第1年，第三个是第2年，让你统计n年后图中的，上三角形个数是多少，（不知道什么是上三角的请看提示）当然为了降低难度，只要找第n年中面积最小的上三角形个数。雯神若有所思“是三角形好看，还是圆形好看呢”


题目输入

多组输入，每组数据输入一个数n（0<=n<=10^18）

题目输出

对于每组数据，输出一个数并对10^9+7取余。

输入/输出样例

输入格式

1
2

输出格式

3
10

C++解答

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

long long n;
const long long mod=1e9+7;
struct Mat{
    long long m[2][2];
};

Mat mut(Mat a,Mat b)
{
    Mat ans;
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
        {
            ans.m[i][j]=0;
            for(int k=0;k<2;k++)
            {
                ans.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
                ans.m[i][j]%=mod;
            }
        }
    }
    return ans;
}

Mat power(Mat a,long long p)
{
    Mat ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=0;i<2;i++)
    {
        ans.m[i][i]=1;
    }
    while(p)
    {
        if(p%2==0)
        {
            a=mut(a,a);
            p/=2;
        }
        else
        {
            ans=mut(ans,a);
            p--;
        }
    }
    return ans;
}

int main()
{
   // freopen( "C.txt", "r", stdin );
    //freopen( "_C.txt", "w", stdout );
    while(cin>>n)
    {
        Mat ans;
        ans.m[0][0]=ans.m[1][1]=3;
        ans.m[0][1]=ans.m[1][0]=1;
        ans=power(ans,n);
        cout<<ans.m[0][0]%mod<<endl;
    }
    return 0;
}
请先登陆