a835: F. 小駿的神奇K維空間
標籤 : 111學年度上學期進階班期中考 priority_queue
通過比率 : 11人/16人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-12-24 22:13

內容

小駿很喜歡數學,尤其是幾何的部分

最近他研究完矩形了,現在他開始往更高維空間發展

他想要畫出心中最完美的$K$維空間超方體

但怎麼畫就是畫不出來

 

有天他為了畫超方體,他熬夜熬到了三點半

然後因為太累了,所以就直接睡死了

他夢到了一大堆的數字,他數了數,發現有$N$個正整數

這時他想到,會不會他心中最完美的超方體就跟邊長有關

於是他決定把這些數字記起來

等他醒來後就能用這些數字畫出超方體

 

過了半小時,他醒了

他把所有數字寫在了紙上

決定每次找$K$個不同的數字為各維度的邊長(值可以相同,但不能是同一個數字)

然後一直畫超方體

最後,他發現他理想的超方體剛好就是超體積最小的矩形

然後他就去睡了

 

這時你剛好走到了他旁邊,看了一眼他畫的所有超方體

你這時也好奇他心中最完美的超方體是什麼

但你懶得一個一個畫,所以你決定就用那$N$個數字自己算出答案

然後你就開始算了

輸入說明

多筆測資,

第一行輸入一數$T$

後重複$T$次:

        輸入兩數$N, K$,代表有$N$個數字,有$K$個維度

        輸入$N$個數$a_i$,代表那$N$個數字

輸出說明

輸出最完美超方體的超體積

範例輸入
2
5 3
2 4 6 5 4
6 4
7 5 1 3 6 8
範例輸出
32
90
測資資訊:
記憶體限制: 16 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <10M
公開 測資點#2 (50%): 1.0s , <50M
提示 :

$K$維超方體的超體積為$l_1 *l_2 * l_3 * \cdots * l_K$,$l_i$為第$i$維的邊長

因為超體積可能會超大,所以請將答案$mod\ 10^9+7$

 

第一筆範例測資:選$2,\ 4,\ 4$(因為他們是兩個不同位子的$4$,所以可以選)

第二筆範例測資:選$1,\ 3,\ 5,\ 6$

 

$20\% $測資:$N = 10^4$

$50\% $測資:$N = 10^6$

$100\% $測資:$N = 2.5*10^6,\ 4 \leq K \leq 10^3,\ 1 \leq a_i \leq 10^4,\ T = 2$

 

測資於$2022/11/10\ 10:57:52 PM$加強完成

標籤:
111學年度上學期進階班期中考 priority_queue
出處:
[管理者:
chrislaiisme (卍乂_第11屆ㄟ進階助教 a.k.a. ...)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」