309547: CF1696H. Maximum Product?

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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\} $ .

Input

题意翻译

定义关于参数 $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$ 个集合。

Output

**题目大意:**

定义一个函数 $ 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 ```

加入题单

上一题 下一题 算法标签: