算法题14 小Q歌单，牛客网，腾讯笔试题

算法题14 小Q歌单，牛客网，腾讯笔试题

题目：

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

输出描述：

输出一个整数，表示组成歌单的方法取模。因为答案可能会非常大，所以输出对1000000007取模的结果。

输入示例：

5

2 3 3 3

输出示例：

9

解题方法：

方法一、暴力搜索，枚举其组合数。

# -*- coding:utf-8 -*-

mod = 1000000007

K = int(input())

A, X, B, Y = list(map(int, input().split()))

#获得阶乘的值

def get_factorial(x):

    if x==0 or x==1:

        return 1

    else:

        return x*get_factorial(x-1)

def get_permutation(m,n):

    first=get_factorial(n)

    second=get_factorial(m)

    third=get_factorial(m-n)

    return second//(first*third)

ans = 0

for i in range(X+1):

    for j in range(Y+1):

        if A*i+B*j==K:

            one = get_permutation(X, i)

            two = get_permutation(Y, j)

            ans += (one*two) % mod

print(ans%mod)

方法二、动态规划。

代码如下：

# -*- coding:utf-8 -*-

mod = 1000000007

K = int(input())

A, X, B, Y = list(map(int, input().split()))

arr = [[0 for i in range(101)] for j in range(101)]

arr[0][0] = 1

for i in range(1,101):

    arr[i][0] = 1

    for j in range(1,101):

        arr[i][j] = (arr[i-1][j-1]+arr[i-1][j]) % mod

ans = 0

for i in range(X+1):

    if (i*A <= K and (K-A*i) % B == 0 and (K-A*i)//B <= Y):

        ans = (ans +(arr[X][i]*arr[Y][(K-A*i)//B]) % mod) % mod

print(ans)