当前位置: 代码迷 >> 综合 >> 2020校招笔试记录7.31
  详细解决方案

2020校招笔试记录7.31

热度:55   发布时间:2024-02-04 23:42:17.0

1. 小明有n头奶头,并且每头奶牛的颜色为m种中的一种,小明要带n奶牛出去的方案一共有多少种?(注意可以带0头奶牛,并且带出的奶牛即使颜色相同数量相同,那么也是不一样的组合,因为每只奶牛体重是不同的)

举例假设n=3,m=2

小明带出0头奶牛的方案为1种;

小明带出1头奶牛的方案为C3_1*2种;

小明带出2头奶牛的方案为C3_2*2^2种;

小明带出3头奶牛的方案为C3_3*2^3种;

因此总计27种。

按该规律可推导出组合数的方程如下

预备复习知识

  只要一降一升初始从0开始到n,且a和b系数相加等于n就能推导出前面

对于这个公式的理解,可以抽象一下:我们可以把看成原本的n个元素中加入了一个新元素,那么根据分类计数原理,我们之前已经求出的组合数中显然少了含有这种新元素的情况。那么就把它加上就好。因为选中这个新元素必定要把一种老元素剔除掉,所以应该加上。

模运算:

1.幂模p : (a^b) % p = ((a % p)^b) % p

2.模p加法:(a + b) % p = (a%p + b%p) % p

3.模p减法:(a - b) % p = (a%p - b%p) % p

4.模p乘法:(a * b) % p = ((a % p)*(b % p)) % p

2.现有n个人,要从这n个人中选任意数量的人组成一只队伍,再在这些人中选出一名队长,求不同的方案对10^9+7取模的结果。如果两个方案选取的人的集合不同或选出的队长不同,则认为这两个方案是不同。