[46无验证]拼硬币-字节跳动2018秋

1.题目描述

现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为纪念币，每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的面值？

• 输入描述:
  第一行三个整数n1,n2,m，分别表示普通币种类数，纪念币种类数和目标面值
  第二行n1个整数，第i种普通币的面值a[i]。保证a[i]为严格升序。
  第三行n2个整数，第i种纪念币的面值b[i]。保证b[i]为严格升序。
  对于30%的测试，保证1<=n1+n2<=10,1<=m<=100,1<=a[i]<=100,1<=b[i]<=100
  对于100%的测试，保证1<=n1+n2<=100,1<=m<=100000,1<=a[i]<=100000,1<=b[i]<=100000输出描述:
  输出一行，包含一个数字x，表示方法总数对1000000007（1e9+7）取模的结果。
• 注意：不要忘记取模！
• 备注:
  两个方法，它们任意一种或以上的硬币数量不同，则认为是两种拼法。
• 输入示例:

  3 1 5
  1 2 3
  1
  

• 输出示例:

  9
  

• 说明:
  (x)代表面值为x的普通币，[x]代表面值为x的纪念币，样例所有方法数如下：
  (1)(1)(1)(1)(1)
  (1)(1)(1)(2)
  (1)(1)(3)
  (1)(2)(2)
  (2)(3)
  (1)(1)(1)(1)[1]
  (1)(1)[1](2)
  (1)[1](3)
  [1](2)(2)

2.题目解析

典型的背包问题，普通币是完全背包问题，纪念币是0/1背包问题。
普通币与纪念币选择是相互独立的，所以计算两者总计方法数使用加法原理。

3.参考答案