Description

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

Input

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s

Output

每次的方法数

Sample Input

1 2 5 10 2
3 2 3 1 10
1000 2 2 2 900

Sample Output

4
27

HINT

数据规模
di,s<=100000
tot<=1000

【分析】

不是数学吗？容斥也算数学吧...

进行一下预处理，求出在可以任取硬币的条件下f(i) 为取得价值为i的方案总数。

然后容斥用总超过限制-1超过限制-2超过限制-3超过限制-4超过限制+1、2超过限制...

怎么算1超过限制？设s为总价值，1的限制量为d[i]，价值为c[i],则1超过限制量为f[s - (d[i] + 1) * c[i]]。

代码复杂度很低，不写了。

最新文章

  1. 高性能Javascript--高效的数据访问
  2. Node.js在Chrome进行调试
  3. Xamarin的不归路-生成安卓错误2
  4. asp.net 301重定向代码
  5. iOS UIView上添加mp4视频
  6. 我的Android六章:Android中SQLite数据库操作
  7. Socket通信的理解
  8. java生成base64编码的png
  9. java中特殊的String类型
  10. nvl
  11. python其中一个子线程，则退出全部线程，再退出进程
  12. 用 Gearman 分发 PHP 应用程序的工作负载
  13. Ubuntu 安装Chrome步骤
  14. 远程连接mysql,mysql如何开启远程连接
  15. javascript笔记—面向对象
  16. C#中对值类型和引用类型的一点认识
  17. Struts2 语法--验证方式:
  18. SQL Server-聚焦NOLOCK、UPDLOCK、HOLDLOCK、READPAST你弄懂多少？（三十四）
  19. JAVA基础——最简单的多重循环程序
  20. Spinner之下拉多选，监听ID后显示不同Frgment页面

热门文章

  1. POJ3641-Pseudoprime numbers（快速幂取模）
  2. linux select 与 阻塞( blocking ) 及非阻塞 (non blocking)实现io多路复用的示例
  3. 问题.NETSystem.Data.OleDb.OleDbException 操作必须使用一个可更新的查询
  4. python 实战
  5. python module的结构
  6. play wav sound
  7. wechat客户端修改
  8. OpenOffice的安装与启动
  9. cocosbuilder中的Callbacks和sound effects
  10. Android开发百度地图（一）--显示基本地图