#577. 货币系统 Money Systems

货币系统 Money Systems

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

母牛们不但创建了它们自己的政府而且选择了建立了自己的货币系统。由于它们特殊的思考方式,它们对货币的数值感到好奇。

传统地,一个货币系统是由 1,5,10,20,25,50,100\red{1,5,10,20,25,50,100} 的单位面值组成的。

母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。

举例来说, 使用一个货币系统 (1,2,5,10,)\red{(1,2,5,10,…)} 产生 18\red{18} 单位面值的一些可能的方法是: 18×1,9×2,8×2+2×1,3×5+2+1\red{18×1,9×2,8×2+2×1,3×5+2+1},等等。

写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。保证总数在 64\red{64} 位带符号整数的范围内。

输入格式

第一行两个整数:货币系统中货币的种类数目 V(1V25\red{V(1≤V≤25)}。要构造的数量钱是 N1N10,000\red{N(1≤N≤10,000)}

第二行 V\red{V} 个整数,代表所有可用的货币的面值。

输出格式

单独的一行,包含用这 V\red{V} 种硬币凑足 N\red{N} 单位货币的方案数。

样例

输入样例

3 10
1 2 5

输出样例

10

DP 练习

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-3-4 15:00
结束于
2023-3-11 12:00
持续时间
165 小时
主持人
参赛人数
46