CF1696H Maximum Product?

给定一个正整数 $k$。对于一个整数多重集 $S$，定义 $f(S)$ 如下： - 如果 $S$ 中的元素个数小于 $k$，则 $f(S)=0$。 - 否则，$f(S)$ 等于从 $S$ 中恰好选出 $k$ 个整数所能得到的最大乘积。 更正式地，设 $|S|$ 表示 $S$ 中元素的个数。那么， - 如果 $|S|

输入的第一行包含两个整数 $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$ 取模。

考虑第一个样例。根据定义有： - $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\}$。 由 ChatGPT 4.1 翻译