51Nod 1013-3的幂的和

1013 3的幂的和

基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题

题目链接

关注

求：3^0 + 3^1 +...+ 3^(N) mod 1000000007

Input

输入一个数N(0 <= N <= 10^9)

Output

输出：计算结果

Input示例

Output示例

题解：

由等比数列的前n相和，我们可以得到一个式子。

现在只需求这个除法取模即可。

除法取模需要用到逆元。

具体的推到方法我已融汇贯通，解释不了。总之，a/b%mod只要求出一个数字就行，可以转化为乘法取模。

b*x%mod=1求出x，结果为a/b%mod=a*x%mod。

参考博客：点击打开

笔记：

1.除法取模要用到逆元

2.（A*B）%C=(A%C*B%C)%C

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007  
#define ll long long int
ll Pow(ll a,ll n)
{
	ll res=1;
	while(n)
	{
		if(n&1)
		{
			res=(res*a)%MOD;
		}
		a=(a*a)%MOD;
		n>>=1;
	}
	return res;
}
int main()
{
	ll n;
	scanf("%lld",&n);	
	ll sum=(Pow(3,n+1)-1)*500000004%MOD;
	printf("%lld",sum);
	return 0;
}