【SSL_2020.10.26】まほう部落

本文主要是介绍【SSL_2020.10.26】まほう部落，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

まほう部落

---

解题思路

作为这套题中第二难的题目，这竟然是第一题…
这道题看起来很简单，然后我们看一眼数据：哇，竟然是 $n<=1000000000$ ！
然而这个数据只能做 $O({\log }_{2}n)$ ，我们又仔细看了一眼题目：这很明显是等比数列求和。等比数列求和的公式我们都知道啦，就是：
$$S^n=\frac{a_1(1-q^n)}{1-q}或S^n=\frac{a_1-a_{n}q}{1-q}$$
其中的 $q^n$ 我们就可以用 快速幂 来求，这恰好是 ${\log }_{2}n$ 的算法！
然而，下面的我就也不是很懂了：逆元
逆元好像就是在 $\frac{a}{b}$ % $c$ 的时爆精度的情况，所以我们要将除法转换成乘法…… （口胡不下去了）

code

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;const ll mod=1000000007;ll n;ll ksm(ll x,ll y)
{ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;
}int main()
{cin>>n;cout<<(ksm(3,n+1)-1)*(mod+1)/2%mod<<endl;
}

这篇关于【SSL_2020.10.26】まほう部落的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---