首页 > 代码库 > UVa 11609 - Teams
UVa 11609 - Teams
题目:n个人中取出k个人组成一个小组,并且其中有一名组长,问有多少种取法。
分析:分治、组合数学。F(n) = C(n,1)*1 + C(n,2)*2 + ... = sum(C(n,i)*i)
推导:C(n,i)*i=n*...*(i+1)/ [i*(i-1)*...*1] * i=n * [(n-1)*...*i]/ [i*...*1]=C(n-1,i)*n
F(n)= n*sum(C(n-1,i))= n * 2^(n-1)
利用快速幂求解即可。
说明:使用long long防止溢出;用%I64d竟然PE(⊙_⊙)。
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; long long N,MOD = 1000000007; long long spow( long long x, long long n ) { if ( n == 0LL ) return 1LL; if ( n == 1LL ) return x%MOD; long long v = spow( x, n/2LL ); if ( n%2LL == 1LL ) return ((v*v)%MOD*x)%MOD; else return (v*v)%MOD; } int main() { int T; while ( cin >> T ) for ( int t = 1 ; t <= T ; ++ t ) { cin >> N; printf("Case #%d: %lld\n",t,spow(2LL,N-1LL)*N%MOD); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。