描述
Tony最近喜欢上了龙之谷游戏，所以他想叫上他的好友组建一个公会来一起享受这款游戏。
Tony一共有n个好友，他可以叫上任意k（1<=k<=n）个好友来组建公会，并且所有好友都会答应他的请求。问Tony一共可以有多少种方案组建这个公会？
只要不是完全相同的人组建的方案视为不同方案，并且Tony至少要叫上一个人。
输入 多组输入，每组一行，输入一个正整数n（1<=n<=1000000000）。
输出 每组输出一行，输出方案数。（对1000000007取膜）
我的想法
这道题是让我们求组合数之和
∑k=1nCkn=2n−1
由于题中所给数据比较大，明显采用快速幂取模来缩短时间。
AC代码
#include<stdio.h>
#define m 1000000007
long quickmul(
long a,
long b);
long mi(
long a,
long b);
int main()
{
long n;
while(
scanf(
"%ld",&n)==
1)
{
getchar();
long ans=
0;
ans=mi(
2,n)-
1;
printf(
"%ld\n",ans%m);
}
return 0;
}
long quickmul(
long a,
long b)
{
long res=
0;
while(b)
{
if(b&
1)
{
b--;
res=(res+a)%m;
}
b=b/
2;
a=(a*
2)%m;
}
return res;
}
long mi(
long a,
long b)
{
long res=
1;
while(b)
{
if(b&
1)
{
b--;
res=quickmul(res,a);
}
b=b/
2;
a=quickmul(a,a);
}
return res;
}
快速幂取模的方法在之前的博客已有介绍，不再赘述。
