纸币问题 2
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目背景
你是一个非常有钱的小朋友。
题目描述
你有 种面额互不相同的纸币，第 种纸币的面额为 并且有无限张，现在你需要支付 的金额，求问有多少种方式可以支付面额 ，答案对 取模。 注意在这里，同样的纸币组合如果支付顺序不同，会被视作不同的方式。例如支付 元，使用一张面值 的纸币和一张面值 的纸币会产生两种方式（ 和 ）。
输入格式
第一行两个正整数 ，分别表示纸币的种数和要凑出的金额。 第二行一行 个以空格隔开的正整数 依次表示这 种纸币的面额。
输出格式
一行一个整数，表示支付方式的数量。
样例 #1
样例输入 #1
6 15
1 5 10 20 50 100
样例输出 #1
42
样例 #2
样例输入 #2
3 15
1 5 11
样例输出 #2
39
提示
对于 的数据，满足 ，； 对于 的数据，满足 ，。
其实小朋友并不有钱。
北辰OI俱乐部算法提高班：动态规划专题（一）
- Status
- Done
- Problem
- 28
- Open Since
- 2023-11-25 0:00
- Deadline
- 2024-12-26 23:59
- Extension
- 24 hour(s)
