Maximum Product?

题意翻译

定义关于参数 $m$ 对于可重集 $S$ 的函数 $f(S)$ 表示在其中选 $m$ 的乘积的最大值，即 $\max_{T\subset S,|T|=m}\prod_{x\in T}x$。 给定参数 $m$ 和可重集 $S$，求对于 $S$ 的所有大小至少为 $m$ 子集 $T$ 的 $f(T)$ 的和，即求 $\sum_{T\subset S,|T|\ge m}f(T)$。 注意本题中可重集中**值相同的每个元素各不相同**，你可以认为本题中将所有元素放入数组中后以下标作为区别标准，即大小为 $n$ 的集合包括空集必然存在 $2^n$ 个集合。

题目描述

You are given a positive integer $ k $ . For a multiset of integers $ S $ , define $ f(S) $ as the following. - If the number of elements in $ S $ is less than $ k $ , $ f(S)=0 $ . - Otherwise, define $ f(S) $ as the maximum product you can get by choosing exactly $ k $ integers from $ S $ . More formally, let $ |S| $ denote the number of elements in $ S $ . Then, - If $ |S|<k $ , $ f(S)=0 $ . - Otherwise, $ f(S)=\max\limits_{T\subseteq S,|T|=k}\left(\prod\limits_{i\in T}i\right) $ . You are given a multiset of integers, $ A $ . Compute $ \sum\limits_{B\subseteq A} f(B) $ modulo $ 10^9+7 $ . Note that in this problem, we distinguish the elements by indices instead of values. That is, a multiset consisting of $ n $ elements always has $ 2^n $ distinct subsets regardless of whether some of its elements are equal.

输入输出格式

输入格式

The first line of input contains two integers $ n $ and $ k $ , where $ n $ is the number of elements in $ A $ ( $ 1\le k\le n\le 600 $ ). The second line of input contains $ n $ integers $ a_1,a_2,\dots,a_n $ , describing the elements in $ A $ ( $ -10^9\le a_i\le 10^9 $ ).

输出格式

Output $ \sum\limits_{B\subseteq A} f(B) $ modulo $ 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

说明

Consider the first sample. From the definitions we know that - $ 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 $ So we should print $ (0+0+0+0-2-4+8+8)\bmod (10^9+7)=10 $ . In the second example, note that although the multiset consists of three same values, it still has $ 8 $ distinct subsets: $ \varnothing,\{1\},\{1\},\{1\},\{1,1\},\{1,1\},\{1,1\},\{1,1,1\} $ .

**题目大意：**

定义一个函数 $ f(S) $，对于参数 $ m $ 和可重集 $ S $，它表示从 $ S $ 中选取 $ m $ 个元素的乘积的最大值，即 $ \max_{T\subset S,|T|=m}\prod_{x\in T}x $。给定参数 $ m $ 和可重集 $ S $，求对于 $ S $ 的所有大小至少为 $ m $ 的子集 $ T $ 的 $ f(T) $ 的和，即求 $ \sum_{T\subset S,|T|\ge m}f(T) $。注意，可重集中的每个元素虽然值相同，但是它们是不同的（可以通过索引区分）。

**输入输出数据格式：**

- **输入格式：**
- 第一行包含两个整数 $ 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_{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(S) $，对于参数 $ m $ 和可重集 $ S $，它表示从 $ S $ 中选取 $ m $ 个元素的乘积的最大值，即 $ \max_{T\subset S,|T|=m}\prod_{x\in T}x $。给定参数 $ m $ 和可重集 $ S $，求对于 $ S $ 的所有大小至少为 $ m $ 的子集 $ T $ 的 $ f(T) $ 的和，即求 $ \sum_{T\subset S,|T|\ge m}f(T) $。注意，可重集中的每个元素虽然值相同，但是它们是不同的（可以通过索引区分）。 **输入输出数据格式：** - **输入格式：** - 第一行包含两个整数 $ 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_{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 ```