首页 > 代码库 > uva11609(组合数学，快速幂)
uva11609(组合数学，快速幂)
先选人，再从这些人里选一个队长，方案总数：C(i,1)*C(n,i)（其中i从1到n）的总和。
这个公式显然不能在时限内暴力算出来，需要变形和推导出更简单的来。
用到组合数里面这个公式：C(n,k)*C(k,r)=C(n,r)*C(n-r,k-r)（其中r<=k）
一变换以后就可以推出最后结果就是n*(2^n-1)，n比较大，所以再用下快速幂就好了。
这里从实际模型出发解释一下这个组合数公式：
有n个球，从中选k个，再从k个里选r个做上标记，有多少选法？
一种思路就是先选k个在从k个里选r个，结果为C(n,k)*C(k,r)。
另一种思路是先选r个标记上，再选(k-r)个，结果为C(n,r)*C(n-r,k-r)。
两个结果必然相等，所以C(n,k)*C(k,r)=C(n,r)*C(n-r,k-r)成立。
对于这道题，其实就可以直接理解为先选一个队长，然后再选其它人。
小结：组合数学的题，有时变换一下选择的顺序就会有意外惊喜！
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>using namespace std;#define INF 1000000000#define eps 1e-8#define pii pair<int,int>#define LL long long intconst int mod=1000000007;int T,n;LL get(LL x,int n){ LL a=1; while(n>=1) { if(n%2==0) { x*=x; x%=mod; n/=2; } else { a*=x; a%=mod; n--; } } return a;}int main(){ //freopen("in6.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); int cas=1; while(T--) { scanf("%d",&n); LL ans=((LL)n*get(2LL,n-1))%mod; printf("Case #%d: %lld\n",cas++,ans); } //fclose(stdin); //fclose(stdout); return 0;}
uva11609(组合数学，快速幂)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。