题目来源：Problem - 185A - Codeforces
题目大意：
矮人种植了一种非常有趣的植物，它是一个“向上”的三角形。这种植物有一个有趣的特点。一年后，“向上”的三角形植物分成四个三角形植物：其中三个指向“向上”，一个指向“向下”。再过一年，每个三角形植物分成四个三角形植物：其中三个方向与母植物相同，一个方向相反。然后每年这个过程都会重复。下图说明了这一过程。
帮助小矮人找出n年内有多少“向上”的三角形植物，输出除以1000000007（1e9+7）的余数。数据范围：0 ≤ n ≤ 10^18。
题目思路：找规律发现，结果=1+2+3+…+2^n mod 1e9+7=(1+2^n)*(2^n)/2 mod 1e9+7。要求2^n，循环复杂度O(n)肯定TLE(至少需要10^9秒,即31年），因此要使用快速幂。
什么是快速幂呢？
顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。
快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
让我们先来看一个简单的例子：
3^10=3*3*3*3*3*3*3*3*3*3
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)
3^10=(3*3)^5
3^10=9^5
9^5=（9^4）*（9^1）
9^5=（6561^1）*(9^1)
那么怎样用c++程序实现快速幂呢？大家先看一段讲解小视频：
所以我们来 look look 一道经典快速幂题:
输入：三个不超过 10000 的正整数 x，p，m。
输出：x^p mod m的值。
#include<iostream>
using namespace std;
int x, p, m, i, result;
int main(){
cin >> x >> p >> m;
result = 1;
while (p)
{ if (p % 2 == 1)
result = result*x%m;
p /= 2;
x = x*x%m;
}
cout << result << endl;
return 0;
}看完讲解视频以及基础习题，相信你已经基本掌握快速幂了。
因此回归正题，继续探究 A. Plant 。
AC代码：
#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long quickpow(long long x,long long y){
long long ret=1;
while(y){
if(y%2) ret=ret*x%mod;
y/=2;
x=x*x%mod;
}
return ret;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
long long n,ans; cin>>n;
ans=(quickpow(2,n)%mod)*((quickpow(2,n)+1)%mod);
ans=ans/2%mod;
cout<<ans;
return 0;
}
//ACplease!!!最后送大家一个小彩蛋：
点击链接免费下载Codeforces 185A - Plant 全测试点49个！文章来源：https://www.toymoban.com/news/detail-514878.html
好了，下期再见啦！文章来源地址https://www.toymoban.com/news/detail-514878.html
到了这里，关于Codeforces 185A - Plant（矩阵快速幂）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
