問題一覧 > 通常問題

No.1359 [Zelkova 3rd Tune] 四人セゾン

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 126
作問者 : KazunKazun / テスター : nok0nok0
0 ProblemId : 5152 / 出題時の順位表
問題文最終更新日: 2021-01-22 20:09:55

注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

春の国, 夏の国, 秋の国, 冬の国からそれぞれ $N$ 人ずつ合計 $4N$ 人が集まって大会が催された. この大会の予選を戦うグループとして, 春, 夏, 秋, 冬の国それぞれ1人ずつからなる $N$ 個のグループ $G_1,\dots,G_N$ を作る. また,この大会の各参加者にはレーティングが設定されており, この値を利用し以下の値を定義する.

  • グループ $G_k$ の4人のレーティングの最大値,最小値をそれぞれ $X_k,Y_k$ としたとき, グループ $G_k$ の不公平さ $D_k$ を $D_k:=X_k-Y_k$ と定義する.
  • 予選の不公平さを $\displaystyle \sum_{k=1}^N D_k^K$ で定義する.

予選の不公平さの最小値 $F$ を求めよ. ただし, $F$ は非常に大きくなる可能性があるので, $F$ を $M$ で割った余りを出力せよ. 予選の不公平さを $M$ で割った余りの最小値を求めるのではないことに注意せよ.
ただし, 春, 夏, 秋, 冬の国の $i$ 番目の参加者のレーティングをそれぞれ $P_i,E_i,A_i,H_i$ とする.

制約

  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 10^9$
  • $1 \leq M \leq 10^9$
  • $0 \leq P_i,E_i,A_i,H_i \leq 10^9~(i=1,2,\dots,N)$
  • 入力は全て整数である.

入力

$N\ K\ M$
$P_1\ P_2\ \dots \ P_N$
$E_1\ E_2\ \dots \ E_N$
$A_1\ A_2\ \dots \ A_N$
$H_1\ H_2\ \dots \ H_N$

出力

考えうる全てのグループ分けを考えたときに可能な, 予選の不公平さの最小値を $M$ で割った余りを出力せよ. 改行を忘れないこと.

サンプル

サンプル1
入力
2 2 100
1 1000
1002 2
3 1004
1006 4
出力
45

2グループの分け方をレーティングが $(1,2,3,4), (1000,1002,1004,1006)$ となるようにすると, 2つのグループの不公平さはそれぞれ $3,6$ なので, 予選の不公平さは $3^2+6^2=45$ になる. また, どのようにグループ分けをしても, 予選の不公平さを $45$ 未満にすることはできない.

サンプル2
入力
1 4 10000
5
10
15
20
出力
625

グループ分けは $(5,10,15,20)$ にするしかなく, 予選の不公平さは $15^4=50625$ なので, これを $10000$ で割った $625$ が答えである.

サンプル3
入力
9 20210122 123456789
14 14 21 35 62 37 30 95 4
88 1 68 87 24 20 96 98 7
85 69 67 18 75 37 69 48 7
31 76 67 97 37 99 7 32 47
出力
39598529

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。