题目描述
如果你之前关注过HPUOJ的话,那么你一定听说过杨八方的名字。在去年,很多同学共同见证了杨八方同学的填报志愿、来到学校、军训……或许你曾陪同杨八方一起思考过许多问题,又或者你是刚听说这个名字,这都不是问题。光阴荏苒,杨八方不见踪影已数月之久。然而,杨八方的故事还没有结束,正值第八届河南理工大学程序设计大赛开幕之际,让我们来继续关注一波杨八方的故事吧。
事实上,杨八方最近在苦恼宿舍中与室友的关系。我们知道很多宿舍都有自己的QQ群,杨八方的宿舍也不例外,六个小伙伴都在共同创建的一个QQ群中,没事聊聊天气氛也算融洽。但是,杨八方最近突然震惊的发现一个现象,她的五个室友竟然莫名其妙地共同商量好了一个事情。事情具体是什么不重要,重要的是她并没有看到室友们面对面开过什么小会议,莫非……宿舍除了共同的QQ群外还有一个五人群没加自己?
于是杨八方开始思考,假设两个人及以上便可创建一个QQ群,那么n个人的宿舍最多可能有几个不一样的QQ群呢?
输入
第一行有一个整数T,代表有T组数据。下面T行每行是一个整数n,代表这个宿舍有n个人。
1<=T<=100000
1<=n<=1000000000
输出
对于每一个结果可能很大,所以你只需要输出对1000000007取模的结果。样例输入
2 2 6 样例输出 1 57首先对数据分析,寻找规律
当n=1时s=0;n=2时s=1;s>=3时,s=2^n-(n+1); 由于题目要求要对1000000007取模,所以要用快速幂取模,最后减去(n-1) 注意:当上述方法求得s<0时,s=s+1000000007(因为这一点WA了8次QAQ与校赛银牌无缘(╥╯^╰╥))#include#include typedef long long ll;ll mod_pow(ll x,ll n,ll mod){ ll res=1; while(n>0) { if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res;} int main(){ int t; ll n,s; scanf("%d",&t); while(t--) { scanf("%lld",&n); if(n==1) s=0; else if(n==2) s=1; else { s=mod_pow(2,n,1000000007)-(n+1); if(s<0) s+=1000000007; } printf("%lld\n",s); } return 0;}