题目描述
小Biu所在的部落是一个魔法部落,部落中一共有n+1个人,小Biu是魔法部落中最菜的,所以他的魔力值为1,魔法部落中n个人的魔法值都不相同,第一个人的魔法值是小Biu的3倍,第二个人的魔法值是第一个人的3倍,以此类推。
现在小Biu想知道整个部落的魔法值和是多少?由于答案比较大,请把答案对1e9+7取模之后输出。
输入
输入一个数N(0 <= N <= 10^9)
输出
输出:整个部落的魔法值和模1e9+7。
样例输入
3
样例输出
40
提示
3^0+3^1+3^2+3^3 = 1+3+9+27 = 40
对于20%的数据,n<=100;
对于40%的数据,n<=1000000;
对于100%的数据,n<=1000000000;
#include<bits/stdc++.h> using namespace std; const int N = 1e9+7; typedef long long ll; ll k(ll a,ll b,ll y){ //快速幂取模 ll t = 1; while(b) { if(b%2 != 0) { t = (a*t)%y; b--; } a = (a*a)%y; b /= 2; } return t; } int main() { ll n; cin>>n; ll x = k(3,n+1,N); if((x-1)%2 != 0) { //判断奇偶 x = x + N; //如果是奇数就加上1e9+7让它变成偶数 } x = (x-1)/2; cout<<x<<endl; }