首页 > 代码库 > 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 - 添加好友
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。