20200823腾讯笔试题
程序员文章站
2023-12-21 20:12:22
...
题目描述:
现有n个人,要从这n个人中选任意数量的人组成一只队伍,再在这些人中选出一名队长,求不同的方案对10^9+7取模的结果。如果两个方案选取的人的集合不同或选出的队长不同,则认为这两个方案是不同的。
分析:
因为选择过程与顺序无关,从n个不同元素中取出m个元素的组合数为c(n,m)。则总的方案数为
1 * C(n,1)+2 * C(n,2)+3 * C(n,3)+4 * C(n,4)+…n * C(n,n)
根据数学公式推导,最终上面组合式结果为n2^(n-1)。
思路:因此问题转化为求 n2^(n-1)。为了降低时间复杂度可用 快速幂
代码如下:
mod=1000000007
def Method(n):
res=n*MyPower(2,n-1)
print(res%mod)
def MyPower(a,b):
level=a
result=1
while(b!=0):
if ((b&1)==1):
result = result * level % mod
level=level * level % mod
b = b>>1
return result%mod
if __name__=="__main__":
n=int(input())
Method(n)