[Solution] Maximum Product? Codeforces Solution

[Solution] Maximum Product? Codeforces Solution | Codeforces Problem Solution 2022

H. Maximum Product?

time limit per test

1.5 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You are given a positive integer k$k$. For a multiset of integers S$S$, define f(S)$f(S)$ as the following.

• If the number of elements in S$S$ is less than k$k$, f(S)=0$f(S)=0$.
• Otherwise, define f(S)$f(S)$ as the maximum product you can get by choosing exactly k$k$ integers from S$S$.

More formally, let |S|$|S|$ denote the number of elements in S$S$. Then,

• If |S|<k$|S|<k$, f(S)=0$f(S)=0$.
• Otherwise, f(S)=maxT⊆S,|T|=k(∏i∈Ti)$f(S)=\underset{T\subseteq S,|T|=k}{max}\left(\prod _{i\in T}i\right)$.

You are given a multiset of integers, A$A$. Compute ∑B⊆Af(B)$\sum _{B\subseteq A}f(B)$ modulo 109+7${10}^9+7$.

Note that in this problem, we distinguish the elements by indices instead of values. That is, a multiset consisting of n$n$ elements always has 2n$2^n$ distinct subsets regardless of whether some of its elements are

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 equal.

Input

The first line of input contains two integers n$n$ and k$k$, where n$n$ is the number of elements in A$A$ (1≤k≤n≤600$1\le k\le n\le 600$).

NIT orz! Codeforces Solution

NIT Destroys the Universe Codeforces Solution 

Fishingprince Plays With Array Codeforces Solution

Permutation Graph Codeforces Solution

Placing Jinas Codeforces Solution 

Tree Recovery Codeforces Solution

Fishingprince Plays With Array Again Codeforces Solution

Maximum Product? Codeforces Solution

The second line of input contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$, describing the elements in A$A$ (−109≤ai≤109$-{10}^9\le a_i\le {10}^9$).

Output

Output ∑B⊆Af(B)$\sum _{B\subseteq A}f(B)$ modulo 109+7${10}^9+7$.