欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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)

相关标签: 笔面试试题

上一篇:

下一篇: