j01683. 0/1 恰好方案数 · 林老师的题库

题目描述

有 $n$ 件物品，第 $i$ 件的体积是 $w_{i}$ ，每件至多选一次。

请计算：选出若干件物品，使总体积恰好为 $V$ 的选择方案数。两种方案只要有任意一件物品的取舍不同就算不同方案。

方案数可能很大，请输出它对 $1 0^{9} + 7$ 取模的结果。

第一行两个整数 $n$ 和 $V$ 。

第二行 $n$ 个整数，依次表示每件物品的体积。

一行一个整数，表示总体积恰好为 $V$ 的方案数对 $1 0^{9} + 7$ 取模的结果（凑不出则为 $0$ ）。

输入

3 5
2 3 4

输出

恰好凑出体积 $5$ 的方案只有一种：选第 1、2 件（ $2 + 3 = 5$ ）。

第 1 + 3 件为 $6$ 、第 2 + 3 件为 $7$ 、三件全选为 $9$ ，都不等于 $5$ ；单件也凑不出 $5$ 。