j01686. 恰 V 且 k 件方案数 · 林老师的题库

题目描述

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

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

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

第一行三个整数 $n$ 、 $V$ 和 $k$ 。

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

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

输入

3 2 2
1 1 2

输出

要恰好选 $2$ 件、体积和恰好为 $2$ ：只有「第 1 + 2 件」一种方案（ $1 + 1 = 2$ ）。

只选第 3 件体积为 $2$ 但件数是 $1$ ，不合「恰好 $2$ 件」；第 1 + 3 件体积为 $3$ ，超出。