j01709. 奇偶体积方案数 · 林老师的题库

题目描述

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

请计算：选出偶数件物品，且总体积恰好为 $V$ 的选择方案数（一件都不选也按「 $0$ 件、偶数」算，但它的体积和为 $0$ ，只有 $V = 0$ 时才相关；本题 $V \geq 1$ ）。两种方案只要有任意一件物品的取舍不同就算不同方案。

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

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

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

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

输入

3 2
1 1 2

输出

体积和恰好为 $2$ 的选法：选第 3 件（ $1$ 件，件数是奇数，不合要求）；选第 1 + 2 件（ $2$ 件，偶数，体积 $1 + 1 = 2$ ✅）。

所以符合条件的方案数只有 $1$ 。