← 返回题目列表

Codeforces · 1696/H

H. 最大乘积?

中文机器翻译题面 查看原题

给你一个正整数$$$k$$$。对于整数多重集 $$$S$$$,定义 $$$f(S)$$$ 如下。

- 如果 $$$S$$$ 中的元素数量小于 $$$k$$$,则 $$$f(S)=0$$$。
- 否则,将 $$$f(S)$$$ 定义为通过从 $$$S$$$ 中精确选择 $$$k$$$ 整数可以获得的最大乘积。

更正式地说,让 $$$|S|$$$ 表示 $$$S$$$ 中的元素数量。然后,

- 如果 $$$|S|<k$$$,则 $$$f(S)=0$$$。
- 否则,$$$f(S)=\max\limits_{T\subseteq S,|T|=k}\left(\prod\limits_{i\in T}i\right)$$$。

给你一个整数多重集$$$A$$$。计算 $$$\sum\limits_{B\subseteq A} f(B)$$$ 模 $$$10^9+7$$$。

请注意,在这个问题中,我们通过索引而不是值来区分元素。也就是说,由 $$$n$$$ 元素组成的多重集始终具有 $$$2^n$$$ 不同的子集,无论其某些元素是否相等。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$,其中 $$$n$$$ 是 $$$A$$$ 中的元素数量 ($$$1\le k\le n\le 600$$$)。

输入的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots,a_n$$$,描述 $$$A$$$ 中的元素 ($$$-10^9\le a_i\le 10^9$$$)。

输出

输出 $$$\sum\limits_{B\subseteq A} f(B)$$$ 模 $$$10^9+7$$$。

示例

输入 #1

3 2
-1 2 4

输出 #1

10

输入 #2

3 1
1 1 1

输出 #2

7

输入 #3

10 4
-24 -41 9 -154 -56 14 18 53 -7 120

输出 #3

225905161

输入#4

15 5
0 0 2 -2 2 -2 3 -3 -3 4 5 -4 -4 4 5

输出#4

18119684

注意

考虑第一个样本。从定义我们知道

- $$$f(\varnothing)=0$$$
- $$$f(\{-1\})=0$$$
- $$$f(\{2\})=0$$$
- $$$f(\{4\})=0$$$
- $$$f(\{-1,2\})=-2$$$
- $$$f(\{-1,4\})=-4$$$
- $$$f(\{2,4\})=8$$$
- $$$f(\{-1,2,4\})=8$$$

所以我们应该打印 $$$(0+0+0+0-2-4+8+8)\bmod (10^9+7)=10$$$。

在第二个示例中,请注意,虽然多重集由三个相同的值组成,但它仍然具有 $$$8$$$ 不同的子集:$$$\varnothing,\{1\},\{1\},\{1\},\{1,1\},\{1,1\},\{1,1\},\{1,1,1\}$$$。