算法题14 小Q歌单,牛客网,腾讯笔试题
2024-08-27 13:41:36
算法题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)
最新文章
- Mac上更新Ruby
- Oracle 截取字符串
- POJ 3067 Japan(树状数组)
- Linux平台Java调用so库-JNI使用例子
- mingw32-g++.exe: *: No such file or directory错误解决方法
- Android布局详解之一:FrameLayout
- HashMap和Hashtable的区别(1)
- win7 X64可用的单文件IE7 遨游美化版
- 在NGINX作反向代理,CI(CodeIgniter)的PHP框架下限制管理目录的IP的实现
- 墙上时钟时间 ,用户cpu时间 ,系统cpu时间
- ASP.NET Core + Vue.js 开发
- 压力测试Apache
- 20175211 2017-2018-2 《Java程序设计》第六周学习记录
- DedeCMS上传视频
- 整合Spring和SpringMVC
- RC4被JDK8默认禁用导致腾讯QQ邮箱无法访问
- [UE4]RPC,远程调用
- virtualenv 安装及使用[转]
- Socket网络编程(TCP/IP/端口/类)和实例
- hdu 1732 bfs
热门文章
- Atitit.nosql&#160;api&#160;标准化&#160;以及nosql数据库的实现模型分类差异
- Knockout JS 演示样例
- Creating Dialogbased Windows Application (3) / 创建基于对话框的Windows应用程序(三)Checkbox的应用、窗体置顶、设置图标 / VC++, Windows
- Java联网技术之一TCP socket
- PHP基础之Autoload
- abp的权限与导航菜单的关系
- hdu2068 RPG的错排 错排+组合
- Spring Java-based容器配置(二)
- 高通音频 媒体喇叭增益隐藏参数(一个QACT无法修改的参数)
- day11函数的进阶动态参数,命名空间,作用域,第一类对象