腾讯笔试题：小Q的歌单解析

题目描述： 

       小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，请问有多少种组成歌单的方法。

了解题意以后我们先来学习一下关于二项式系数、排列组合、杨辉三角形的有关知识：

1、二项式系数

2、杨辉三角形

3、杨辉三角形与二项式系数的关系

【奇妙的杨辉三角与二项式系数】- 图解高中数学

杨辉三角形每一行数字都与二项式展开后系数相联系。

        其中 n 代表在杨辉三角上行数, 且初始值为 0. 当 n 等于不同的整数展开多项式, 得到的每一项的系数, 都会跟杨辉三角对应行数的一整行数字完全一致。

4、排列组合

我把重点摘下来了（摘自知乎）：如何通俗的解释排列公式和组合公式的含义？

5、笔试题分析

        分析：这道题比较好的处理方法也最容易理解的是用组合数来求解，说到组合数就很容易想到这道题和我们高中做的从两个盒子里取小球的排列组合题。

        此题可以转换为这样一道数学题，有两个盒子，一个盒子里装有3个红球，一个盒子里装有3个白球，红球代表2分，白球代表3分，则从两个盒子中任意拿球使其分数等于9的拿法有多少种。

        这样就会想如果拿了0个红球，白球有多少种拿法，如果拿了1个、2个、3个红球，白球各有多少种拿法。

        再者，将球的数量和球的分数换成未知的量：即有两个盒子，一个盒子里装有X个红球，一个盒子里装有Y个白球，红球代表A分，白球代表B分，则从两个盒子中任意拿球使其分数等于K的拿法有多少种。很显然就和面试题一样了，可以想到假设拿了 i 个红球（ i  <= X），需要满足条件（ i * A <= K : 分数不能超过K）&&（（ K - i* A）% B == 0  ：确保分数相加等于K） &&  （（ K - i* A）/  B  <= Y  :不能超过白球的数目），将满足条件的结果相加起来就是最后的结果。

        而当满足条件后从各自的盒子里拿球就有不同的拿法，是很典型的排列组合问题，对于这道题我们可以建一个二维数组来存这些组合数，行标代表排列组合公式的下标，列标代表排列组合公式的上标，具体的存法和杨辉三角有些类似

接下来我们看笔试题C语言代码：

运行结果：

java代码：

运行结果：