首页 > 代码库 > SHU 413 - 添加好友

SHU 413 - 添加好友

题目链接:http://acmoj.shu.edu.cn/problem/413/

不难发现,这题是求C(n,1)+C(n,2)+C(n,3)+……+C(n,n-1)+C(n,n)

根据二项展开式有(a+b)^n = C(n,0) * (a^n) * (b^0) + …… + C(n,n) * (a^0) * (b^n)

故,令a=b=1,有C(n,0) + …… + C(n,n) = 2^n,故C(n,1)+C(n,2)+C(n,3)+……+C(n,n-1)+C(n,n) = 2^n-1

因此这题就很简单了

 1 #include<cstdio>
 2 #define MOD 1000000007
 3 typedef long long ll;
 4 ll n;
 5 ll pow(ll a,ll b){
 6     ll r=1,base=a%MOD;
 7     while(b){
 8         if(b&1) r*=base , r%=MOD;
 9         base*=base;
10         base%=MOD;
11         b>>=1;
12     }
13     return r;
14 }
15 int main()
16 {
17     while(scanf("%lld",&n)!=EOF)
18     {
19         printf("%lld\n",(pow(2,n)-1)%MOD);
20     }
21 }

 

SHU 413 - 添加好友