腾讯2018笔试题，小Q的歌单

「爱情、让人受尽委屈。」 2022-03-31 13:44 295阅读 0赞

【题目描述】小 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 取模的结果。

输入示例：

2 3 3 3

输出示例：

--------------------

这题考察组合数，从n首歌中取出k首歌的方法个数为：Cnk，可以使用一个数组c\[n\]\[k\]表示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
根据杨辉三角形可以写出组合数的动态规划算法。c\[n\]\[k\] = c\[n-1\]\[k\] + c\[n-1\]\[k-1\]（例如图片中28 = 7 + 21）。写出组合数之后，就可以看到就是一个排列组合遍历的问题

--------------------

代码：

c = [([0] * 105) for i in range(105)]
    mod = 1000000007
    c[0][0] = 1
    for i in range(1, 101):
        c[i][0] = 1
        for j in range(1, 101):
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod    #杨辉三角形更新组合数
    K = int(input())
    A, X, B, Y = map(int, input().split())
    ans = 0
    for x in range(X + 1):
        y = int((K - A * x) / B)  #第二个歌单的数量
        if x * A <= K and (K - A * x) % B == 0 and y <= Y:
            ans = (ans + (c[X][x] * c[Y][y]) % mod) % mod
    print(ans)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220331/bd91e55483bf434c815b03a5b742427e.png