#1004. 【提高】中国梦

【提高】中国梦

说明

小 Z 整理完房间时间已经不早了,简单洗漱一下就上床睡觉了,自从进入初三后小 Z 已经有很久没有做梦了,不做梦的主要原因是学习强度太大加上睡得较晚,一旦睡着就睡 得特别沉,沉到没有梦的地步。今晚小 Z 的大脑皮层特别兴奋,大约是由于白天在 CZ 中 学上的课实在太精彩了,这不小 Z 刚睡着就进入了梦乡。在梦里小 Z 梦见自己代表祖国赴 B 国参加了国际信息学奥林匹克竞赛(International Olympiad in Informatics,简称 IOI)并获得了金牌,颁奖会结束后小 Z 想到附近的超市去买些礼物带回国送给班里的小 伙伴们,小 Z 心想 B 国的巧克力代表了爱的愿望、大众的迷恋,是食物中的王者,早在 19 世纪就已经闻名于世了,给小伙伴们每人买一盒巧克力肯定会大受欢迎。于是小 Z 一进超市就直奔装有巧克力的货架,一口气拿了 40 盒 Godiva 巧克力,然后到收银台去排队结帐, 轮到小 Z 结账时,他发现自己身上只有一张大面额的 B 国钞票了,于是他把这张钞票递了 过去,收银员迅速在收银机上算出了要找给小 Z 的金额,然后打开钱柜准备找钱,小 Z 看 到钱柜里的硬币按面额从大到小整整齐齐地摆放着,一种面额的硬币垒成一列,见此情景 小 Z 一下就来了灵感,心想少年宫正在为本次活动征集试题呢,就拿这个找零问题考考小 朋友们不是挺好吗?小 Z 回到宾馆立刻打开笔记本开始命题:

已知收银员要找给小 Z 的金 额 N、钱柜里的硬币种类 K 以及 K 种硬币的面额,计算有多少种不同的找零方法? 这里的 “不同”是指所找零钱至少有一种硬币的数量不相同。假设现在只有 2 种硬币,一种面额是 5 分,另一种面额是 1 分,要找给小 Z 的金额是 8 分钱,可以给小 Z 找 1 个五分硬币加3 个一分硬币,或者找 8 个一分硬币。用 3 个一分硬币加 1 个五分硬币本质上与 1 个五分硬币加 3 个一分硬币没有任何区别,因此只可以用两种不同的方式找出八分钱。

输入格式

输入数据第一行有两个用空格隔开的整数 NN K K,其中 1N3001≤N≤300,表示超市收银员 要找给小 Z 的金额,1K81≤K≤8,表示收银员的钱柜里共有K K 种不同面额的硬币。

第 2 到K K+1 行每行包含一个正整数Ci C_i,其中1Ci100 1≤C_i≤100,表示一种硬币的面额,在输入数据中硬币 面额按降序排列(从最大到最小)。

不同种类的硬币面额各不相同,每种硬币都取之不尽 用之不竭。

输出格式

输出数据仅有一行包含一个整数,表示超市收银员可能的找零方案数。答案保证不会 超出长整型范围。需要注意的是如果没有面额为 1 分的硬币,有些金额将无法找零,此时 结果就输出 0。

样例

83 5
50
25
10
5
1
159

样例解释

输入详解:收银员要找给小 Z 金额 83 分,共有 5 种硬币,面额分别为:50,25,10, 5,1

输出详解:以下是全部 159 种找零方案中的 前 15 种和最后一种:

0×50 0×25 0×10 0×5 83×1
0×50 0×25 0×10 1×5 78×1
0×50 0×25 0×10 2×5 73×1
0×50 0×25 0×10 3×5 68×1
0×50 0×25 0×10 4×5 63×1
0×50 0×25 0×10 5×5 58×1
0×50 0×25 0×10 6×5 53×1
0×50 0×25 0×10 7×5 48×1
0×50 0×25 0×10 8×5 43×1
0×50 0×25 0×10 9×5 38×1
0×50 0×25 0×10 10×5 33×1
0×50 0×25 0×10 11×5 28×1
0×50 0×25 0×10 12×5 23×1
0×50 0×25 0×10 13×5 18×1
0×50 0×25 0×10 14×5 13×1
……………………………………………
1×50 1×25 0×10 1×5 3×1

数据范围

  • 10%的数据满足:N50K3Ci10N≤50,K≤3,C_i≤10
  • 30%的数据满足:N100K5Ci20N≤100,K≤5,C_i≤20
  • 60%的数据满足:N100K7Ci50N≤100,K≤7,C_i≤50
  • 100%的数据满足:N300K8Ci100N≤300,K≤8,C_i≤100