[50]小Q的歌单-腾讯2018秋
2018-11-08 本文已影响28人
jdzhangxin
1.题目描述
小Q有X首长度为A的不同的歌和Y首长度为B的不同的歌，现在小Q想用这些歌组成一个总长度正好为K的歌单，每首歌最多只能在歌单中出现一次，在不考虑歌单内歌曲的先后顺序的情况下，
请问有多少种组成歌单的方法。
- 输入描述：
每个输入包含一个测试用例。
每个测试用例的第一行包含一个整数，表示歌单的总长度K(1<=K<=1000)。
接下来的一行包含四个正整数，分别表示歌的第一种长度A(A<=10)和数量X(X<=100)以及歌的第二种长度B(B<=10)和数量Y(Y<=100)。保证A不等于B。 - 输出描述：
输出一个整数,表示组成歌单的方法取模。因为答案可能会很大,输出对 1000000007 取模的结果。 - 输入示例：
5 2 3 3 3 - 输出示例：
9
2.题目解析
将两种长度的歌的数量进行遍历，如果满足总长度为K，计算该数量的组合下共有多少种不同歌曲的组合方式。所以本题的关键是实现组合函数。
一般来说，时间复杂度是阶乘级的函数是不可用的。这里需要用到杨辉三角。
- 杨辉三角与组合之间的关系：
组合的递推公式
杨辉三角
从上图可见，杨辉三角保存着所有组合数。所以，只要把部分杨辉三角保存起来，求解组合直接查表。对应的C[m][n]就是
数学上规定
3.参考答案
#include <bits/stdc++.h>
using namespace std;
long long c[101][101]; // 保存杨辉三角
const int mod = 1000000007;
void init(int size) {
c[0][0] = 1;
for (int i = 1; i != size; i++) {
c[i][0] = 1;
for (int j = 1; j != size; j++){
// 杨辉三角规则：当前值是上一行的两个肩上的值之和
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
}
int main() {
// 构建杨辉三角
init(101);
// 获取输入参数
int k = 0;// 歌单总长度
scanf("%d",&k);
int a = 0; // 第一种歌曲长度
int x = 0; // 第一种歌曲数量
int b = 0; // 第二种歌曲长度
int y = 0; // 第二种歌曲数量
scanf("%d%d%d%d",&a,&x,&b,&y);
int res=0;
// 遍历第一种歌曲数量可选用的数目0~x
for (int i = 0; i <= x; i++) {
int sum_a = i*a; // 第一种歌曲长度和
int sum_b = k-i*a; // 第二种歌曲长度和
if (sum_a <= k // 选取的第一种歌曲长度和不超过歌单总长度
&& sum_b%b == 0 // 除去第一种歌曲长度和，剩余长度必须是第二种歌曲长度的整数倍
&& sum_b/b <= y // 第二种歌曲数目不能超过歌曲总数
){
// 组成歌单数目
int count = (c[x][i] * c[y][sum_b/b]) % mod;
res = (res + count) % mod; // 因为可能不止一种方式，多种方式数目累加。
}
}
printf("%d\n", res);
return 0;
}
