Apple Trees Gym – 101845A (矩阵快速幂)

题目链接:https://cn.vjudge.net/contest/256986#problem/A
题意:在第0年有一个0岁的苹果树,苹果树10岁会生16个0岁的苹果树,20岁会生9个0岁的苹果树,30岁会生4个0岁的苹果树,40岁会生一个0岁的苹果树,45岁这个这个苹果树就结束了它悲惨的一生。
思路:一看就是递推关系,n是1e15,所以要用矩阵快速幂。
题解见:http://zyl1213.top/blog/archives/1059
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void cheng(long long a[9][9],long long b[9][9])
{
    long long tmp[9][9];
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            for(int k=0;k<9;k++)
            {
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j]%1000000007)%1000000007;
            }
        }
    }
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            a[i][j]=tmp[i][j];
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    long long n;
    cin>>n;
    if(n==0)
    {
        cout<<"1"<<endl;
        return 0;
    }
    long long tmp=n/5;
    long long a[9][9]=
    {
        0,16,0,9,0,4,0,1,0,
        1,0,0,0,0,0,0,0,0,
        0,1,0,0,0,0,0,0,0,
        0,0,1,0,0,0,0,0,0,
        0,0,0,1,0,0,0,0,0,
        0,0,0,0,1,0,0,0,0,
        0,0,0,0,0,1,0,0,0,
        0,0,0,0,0,0,1,0,0,
        0,0,0,0,0,0,0,1,0
    },b[9][9]=
    {
        1,0,0,0,0,0,0,0,0,
        0,1,0,0,0,0,0,0,0,
        0,0,1,0,0,0,0,0,0,
        0,0,0,1,0,0,0,0,0,
        0,0,0,0,1,0,0,0,0,
        0,0,0,0,0,1,0,0,0,
        0,0,0,0,0,0,1,0,0,
        0,0,0,0,0,0,0,1,0,
        0,0,0,0,0,0,0,0,1
    };
    while(tmp)
    {
        if(tmp%2)
        {
            cheng(b,a);
        }
        cheng(a,a);
        tmp/=2;
    }
    long long ans=0;
    for(int i=0;i<9;i++)
    {
        ans=(ans+b[i][0])%1000000007;
    }
    cout<<ans<<endl;
    return 0;
}

1 thought on “Apple Trees Gym – 101845A (矩阵快速幂)”

aaa进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注