#J. Multiplication 4

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Multiplication 4

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

给你两个数 N,KN,K，从 NN 个数中选出 KK 个使得乘积最大。输出乘积在数学意义上对 109+710^9+7 取模的值。

题目描述

N N 個の整数 A1,…,AN A_1,\ldots,A_N が与えられます。

このなかからちょうど K K 個の要素を選ぶとき、選んだ要素の積としてありえる最大値を求めてください。

そして、答えを (109+7) (10^9+7) で割った余りを 0 0 以上 109+6 10^9+6 以下の整数として出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K A1 A_1 … \ldots AN A_N

输出格式

答えを (109+7) (10^9+7) で割った余りを、0 0 以上 109+6 10^9+6 以下の整数として出力せよ。

样例 #1

样例输入 #1

4 2
1 2 -3 -4

样例输出 #1

12

样例 #2

样例输入 #2

4 3
-1 -2 -3 -4

样例输出 #2

1000000001

样例 #3

样例输入 #3

2 1
-1 1000000000

样例输出 #3

1000000000

样例 #4

样例输入 #4

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

样例输出 #4

999983200

提示

制約

  • 1 ≤ K ≤ N ≤ 2× 105 1\ \leq\ K\ \leq\ N\ \leq\ 2\times\ 10^5
  • ∣Ai∣ ≤ 109 |A_i|\ \leq\ 10^9

Sample Explanation 1

要素を 2 2 個選んだときの積としてありえる値は 2,−3,−4,−6,−8,12 2,-3,-4,-6,-8,12 なので、最大値は 12 12 です。

Sample Explanation 2

要素を 3 3 個選んだときの積としてありえる値は −24,−12,−8,−6 -24,-12,-8,-6 なので、最大値は −6 -6 です。 これを (109+7) (10^9+7) で割った余りである 1000000001 1000000001 を出力します。

Sample Explanation 3

要素を 1 1 個選んだときの積としてありえる値は −1,1000000000 -1,1000000000 なので、最大値は 1000000000 1000000000 です。

Sample Explanation 4

答えを (109+7) (10^9+7) で割った余りを出力してください。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 43ms
  • Powered by Hydro v4.9.27 Community