添加好友（快速幂取模）

“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛D题——添加好友

描述 Tony最近喜欢上了龙之谷游戏，所以他想叫上他的好友组建一个公会来一起享受这款游戏。

Tony一共有n个好友，他可以叫上任意k（1<=k<=n）个好友来组建公会，并且所有好友都会答应他的请求。问Tony一共可以有多少种方案组建这个公会？

只要不是完全相同的人组建的方案视为不同方案，并且Tony至少要叫上一个人。

描述 多组输入，每组一行，输入一个正整数n（1<=n<=1000000000）。

输出 每组输出一行，输出方案数。（对1000000007取膜）

样例输入 2

样例输出 3

---

思路：首先由题目分析知道，方案数是 C(n,1)+C(n,2)+…+C(n,n),第一时间想到的是pow(2,n)-1;但是由于n的范围是（1<=n<=1000000000），所以用pow不但慢而且会溢出。 再一想直接用快速幂的模板就好。

---

快速幂模板，表示a的b次方对p取模

int fast(int a,int b,int p) { long long a1=a,t=1; while(b>0) { if(b&1) t=(t%p)*(a1%p)%p; a1=(a1%p)*(a1%p)%p; b/=2; } return (int)(t%p); }

AC代码

#include<iostream> #include<cstdio> #include<vector> #include<set> #include<algorithm> #include<cmath> using namespace std; int fast(int a,int b,int p) { long long a1=a,t=1; while(b>0) { if(b&1) t=(t%p)*(a1%p)%p; a1=(a1%p)*(a1%p)%p; b/=2; } return (int)(t%p); } int main() { int n; while(scanf("%d",&n) != EOF) { long long x = fast(2,n,1000000007)-1; //注意要-1 printf("%lld\n", x); } return 0; }