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示例

3

Output示例

40

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

long long quickpow(long long m,long long n,long long k)

{

    long long b = 1;

    while (n > 0)

    {

          if (n & 1)

             b = (b*m)%k;

          n = n >> 1 ;

          m = (m*m)%k;

    }

    return b;

}

int main()

{

	long long n,result;

	cin>>n;

	result=(quickpow(3,n+1,1000000007*2)-1+1000000007*2)%1000000007;

	cout<<result/2<<endl;

	return 0;

}

版权声明：本文为博主原创文章，未经博主允许不得转载。