首页 > 试题广场 >

小Q的歌单

[编程题]小Q的歌单

热度指数：18606 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小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取模的结果。

示例1

输入

5
2 3 3 3

输出

算法知识视频讲解

Python

Mrs.Jing

# 组合数 C^(a)_(b)
def cnn(a,b):
    if a == 0:
        return 1
    fz,fm = 1,1
    for i in range(a):
        fz *= (b-i)
    for i in range(a):
        fm *= (i+1)
    return fz//fm

K = [int(x) for x in input().split()][0]
A,X,B,Y = [int(x) for x in input().split()]

# 组合方式, 即求解策略集
zhfs = []
a_max = min(K//A, X)
b_max = min(K//B, Y)
for a in range(a_max+1):
    b = 0
    while a*A + b*B <= K and b <= b_max:
        if a*A + b*B == K:
            zhfs.append([a, b])
        b += 1


ans = 0
if not zhfs:
    print(0)
else:
    for i,j in zhfs:
        ans += (cnn(i,X)*cnn(j,Y))
    print(ans%1000000007)

python 3代码，本人计算机渣的一批，确实没看出来题目和杨辉三角的关系。。

编辑于 2019-08-17 15:58:36 回复(0)

Python

管子_no1

python3

说实话对当前我来说挺难

# 动态规划，模仿背包问题，问题简化为有x+y种物品，其中x种的容积为a，y种的容积为b，背包容积为k，问背包装满一共有多少种解法？
# dp[i][j]: i 代表背包容积, j 代表前 j 个物品, 前 j 个元素恰填满容积为 i 的背包的组合数
k = int(input())
num_list = list(map(int, input().split()))
a, x, b, y = num_list[0], num_list[1], num_list[2], num_list[3]
things = [0] + [a for i in range(x)] + [b for i in range(y)] # 长度为 a+b+1
dp = [[0 for j in range(x+y+1)] for i in range(k+1)]
for i in range(x+y+1):
  dp[0][i] = 1
# 考虑 i > 0
for i in range(1, k+1):
  for j in range(1, x+y+1):
      if things[j] > i:
          dp[i][j] = dp[i][j-1]
      elif things[j] == i:
          dp[i][j] = dp[i][j-1] + 1
      elif things[j] < i:
          if dp[i-things[j]][j-1] != 0: #
              dp[i][j] = dp[i][j-1] + dp[i-things[j]][j-1]
          else:
              dp[i][j] = dp[i][j-1]
print(int(dp[k][x+y])%1000000007)

发表于 2019-08-16 16:18:39 回复(0)

Python

如果当时时光说

m,n=int(input()),list(map(int,input().split()))

s=0

def

m,n=int(input()),list(map(int,input().split()))
s=0
def fact(n):
    if n==1:
        return 1
    return n*fact(n-1)
for i in range(n[1]+1):
    for j  in range(n[3]+1):
        if n[0]*i+n[2]*j==m:
            s=s+fact(n[1])//(fact(n[1]-i)*fact(i))*fact(n[3])//(fact(n[3]-j)*fact(j))
print(s%1000000007)

为什么会出现这种情况，有木有哪个大佬解释一下呀

发表于 2019-08-15 15:53:56 回复(0)

Python

share1722

递归+Cache 本质和01背包问题动态规划解法一致

import sys

def main():
    k = int(sys.stdin.readline().strip())
    line = list(map(int, sys.stdin.readline().strip().split()))
    A, X, B, Y = line[0], line[1], line[2], line[3]
    musics = list()
    musics.extend([A] * X)
    musics.extend([B] * Y)
    print(solver(0, musics, k, dict()) % 1000000007)

def solver(pos, musics, cur, dp):
    if (pos, cur) in dp:
        return dp[(pos, cur)]

    if cur < 0:
        return 0
    if pos == len(musics):
        return 1 if cur == 0 else 0

    for index in range(pos, len(musics)):
        if (index + 1, cur - musics[index]) not in dp:
            dp[(index + 1, cur - musics[index])] = solver(index + 1, musics, cur - musics[index], dp)
        if (index + 1, cur) not in dp:
            dp[(index + 1, cur)] = solver(index + 1, musics, cur, dp)

        return dp[(index + 1, cur - musics[index])] + dp[(index + 1, cur)]

if __name__ == '__main__':
    main()

发表于 2019-06-14 11:33:00 回复(0)

Python

牛客用户568435


	import sys



	if __name__ == "__main__":



	    data=[]



	while True:



	    line = sys.stdin.readline().strip()



	    if not line:



	        break



	    tmp = list(map(int, line.split(" ")))



	    data.append(tmp)



	n=data[0][0]



	l=data[1]



	length=[0]



	for i in range(l[1]):



	    length.append(l[0])



	for i in range(l[-1]):



	    length.append(l[-2])



	def gedan(n,length):



	    dp=[[0 for i in range(len(length))]for i in range(n+1)]



	    for i in range(5):



	        dp[0][i]=1



	    for j in range(1,n+1):



	        dp[j][0]=0



	    for i in range(1,n+1):       



	        for j in range(1,len(length)):



	            if length[j] > i:



	                dp[i][j] = dp[i][j-1]



	            elif length[j] == i:



	                dp[i][j]=dp[i][j-1]+1



	            else:



	                dp[i][j] = dp[i][j-1]+dp[i-length[j]][j-1]               



	    return dp[n][len(length)-1]%1000000007



	print(gedan(n,length))

发表于 2019-06-12 16:40:29 回复(1)

Python

佛系求个offer

#写个python版本的动态规划
k = int(input().strip())
A,X,B,Y = map(int,input().strip().split())
dp = [[0 for i in range(k+1)] for j in range(X+Y)]
list = [A]*X+[B]*Y for i in range(X+Y):
    dp[i][0] = 1 for j in range(1,k+1):
    dp[0][j] = 1 if j ==  list[0] else 0 for i in range(1,X+Y):  for j in range(1,k+1):
        dp[i][j] = dp[i-1][j]+dp[i-1][j-list[i]] if j>=list[i] else dp[i-1][j] print(dp[X+Y-1][k]%1000000007)

发表于 2019-02-16 10:42:52 回复(0)

Python

陳皮味的杨桃

排列组合C

def C(i,a): #排列组合C C(2,10)表示 10个里面取2个

k,c_1,c_2=1,1,1

while k<=i:

c_1=c_1*a

c_2=c_2*k

a=a-1

k=k+1

return int((c_1/c_2))

k=int(input())
a,x,b,y = map(int,input().split()) # A 的长度a 个数x B 的长度b 个数y
s=0
active=0

for i in range(0,x+1):

r=k-a*i

if r%b==0 and r>=0 and (r/b)<=y:

active+=1

j=int(r/b) # 找到(i,j)的组合让ai+bj=k

s=s+(C(i,x))*(C(j,y))

if active>0:

print(s% 1000000007)

else:

print(0)

为什么python3这样就只有60%的正确率！大神求解！！

编辑于 2018-09-17 19:50:29 回复(2)

Python

东不拉

'''    import itertools  K = int(input()) A,X,B,Y = input().split() A,X,B,Y = int(A), int(X), int(B), int(Y)  result = 0  list_X = list(range(X)) list_Y = list(range(Y)) for x in range(X+1):  for y in range(Y+1):  k = A * x + B * y  if k == K:  print("%d = %d * %d + %d * %d"%(k, A, x, B, y))  result_X = list(itertools.combinations(list_X, x))  result_Y = list(itertools.combinations(list_Y, y))  print(result_X)  print(result_Y)  result += len(result_X) * len(result_Y) result = result % 1000000007 print(result) '''  import math def C(n,m):
    m1 = m
    m2 = m
    uper = 1  downer = 1  while(m1>0):
        uper *= n
        m1 -= 1  n -= 1   while(m2>0):
        downer *= m2
        m2 -= 1  return int(uper/downer)
K = int(input())
A, X, B, Y = map(int, input().strip().split(' '))
result = 0 for x in range(X+1): for y in range(Y+1):
        k = A * x + B * y if k == K: print(x,y)
            result += C(X,x) * C(Y,y)
result = result % 1000000007 print(result)




链接：https://www.nowcoder.com/questionTerminal/f3ab6fe72af34b71a2fd1d83304cbbb3

来源：牛客网

您的代码已保存

答案错误:您提交的程序没有通过所有的测试用例

case通过率为70.00%

测试用例:

205

1 92 4 92

对应输出应该为:

580636981

你的输出为:

162025174



这是什么原因？