[HAOI2008]硬币购物

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 coin.in 输出文件 coin.out

【问题描述】

一共有 4 种硬币,面值分别为 c1,c2,c3,c4 。阿Q带着一些硬币去商店买东西，他带了d1枚第一种硬币,d2枚第二种硬币,d3枚第三种硬币,d4枚第四种硬币,若想买一个价值为s的东西,问阿Q有多少种付coins的方法。

比如 c={1,2,5,10},d={3,2,3,1},s=10,一共有4种方法:
10=1+1+1+2+5
10=1+2+2+5
10=5+5
10=10

注意,阿Q可能会去很多次商店,每次带的硬币数量和要买的东西价值可能不一样,你需要对每次都求出方法总数.

【数据输入】

输入文件的第一行是5个整数, c1,c2,c3,c4,tot 分别表示4种硬币的面值和阿Q去商店的次数,下面 tot 行 ,每行5个非负整数,d1,d2,d3,d4,s

【数据输出】

输出有tot行,表示第i次付coins的方法总数,保证答案在int64/long long范围内

【输入样例】
1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

【输出样例】
4
27

【数据范围】

（1）100%的数据,d1,d2,d3,d4,s<=100,000

（2）30%的数据,tot<=50

（3）100%的数据,tot<=1000