求：3^0 + 3^1 +…+ 3^(N) mod 1000000007
Input
输入一个数N(0 <= N <= 10^9)
Output
输出：计算结果
Input示例
3
Output示例
40
这道题很明显需要用到快速求幂，但是简单的快速求幂无法满足这道题的要求，如何求和是一个很重要的问题，求和有一个简单的方法，也有一个复杂的，先说复杂的，虽然复杂却容易理解。
#include <stdio.h>
#define _MOD 1000000007
typedef long long ll;ll c;//快速求幂
ll power(ll a, ll b)
{ll ans = 1;while (b){if (b & 1){ans = (ans * a) % _MOD;b--;}b >>= 1;a = (a * a) % _MOD;}return ans;
}ll sum(ll a, ll k)
{if (k == 1){return a;}c = sum(a, k >> 1); //前k／2个次幂的和//ans等于前k/2个次幂的和加上接着的k/2个次幂的和（前k/2个次幂的和乘以第k/2个数的次幂）ll ans = (c + c * power(a, (k >> 1))) % _MOD;//加上最后一个奇数次方值if (k & 1){ans = (ans + power(a, k)) % _MOD;}return ans;
}int main()
{ll n;scanf("%lld", &n);printf("%lld\n", ((sum(3, n) % _MOD)) + 1);return 0;
}这里的求和函数有着快速求幂的思想，结合了递归来实现了幂的求得，有点意思的题。
另外还有一个很简单很简单的方法，只用一行就可以替代去求和的过程，那就是用到逆元，然而像我这样的数学早已九九归一的人，已经不知道怎么去理解这行代码中蕴含的数学理论，只是知道，把它当作公式一样去记住就好了，让我去理解推一下这个公式，已经不是我现在一时半会儿能做到的，数学家们通过几十年的研究才研究出来的东西，我这数学忘完了的人就无力去推算了，证明公式的正确性的事已经不是我的事情了，所以这里只是看看，记住公式，以后争取用到就好了。
#include<stdio.h>
#define mod 1000000007
typedef long long ll;ll mod_pow(ll x,ll n)
{ll res = 1;while(n > 0){if(n & 1)res = res * x % mod;x = x * x % mod;n >>= 1;}return res;
}int main()
{ll n, ans;scanf("%lld", &n);n++;ans = (mod_pow(3, n) - 1) * 500000004 % mod; //求2的逆元即可.因为2 * ? = 1 (mod 1000000007) ? = 500000004printf("%lld", ans);return 0;
}
总结下来就是先求3的n+1次幂，减去一后，乘以2与mod的逆元，最后再取一下模即可。感觉十分不可思议，根本想不通这个解法的内在原理，但是只知道其具有可行性，所以，记住这个方法，记住这个公式，就已经不错了。