問題一覧 > 通常問題

No.3698 Team Division by Lottery

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 27
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 8301 / 自分の提出
問題文最終更新日: 2026-09-09 23:34:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
チーム機能テストコンテスト (順位表) の他の問題:

Problem Statement

$N$ participants are randomly divided into $K$ teams. $N$ is a multiple of $K$, and every team has exactly $N/K$ members.

All such divisions are chosen with equal probability. Each participant $i$ has $2$ integers $A_i, B_i$, and when participants $i$ and $j$ are on the same team, a friendship value of $A_i B_j + A_j B_i$ is obtained.

Find the expected value of the total friendship value obtained, modulo $998244353$.

Input

$N\ K$
$A_1\ A_2\ \cdots\ A_N$
$B_1\ B_2\ \cdots\ B_N$

$2 \le N \le 2 \times 10^5$
$1 \le K \le N$, and $K$ divides $N$
$0 \le A_i, B_i < 998244353$
All inputs are integers

Output

Output the expected value modulo $998244353$. The value to be found is always a rational number, and its denominator is coprime to $998244353$. Print a newline at the end.

Sample

Sample 1
Input
4 2
1 2 3 4
1 1 1 1
Output
10

The probability that any given pair is on the same team is $(2-1)/(4-1) = 1/3$. The total friendship value over all pairs is $30$, so the expected value is $10$.

Sample 2
Input
2 1
5 7
2 3
Output
29

Since $K = 1$, the $2$ participants are always on the same team. Exactly $5 \times 3 + 7 \times 2 = 29$ is always obtained.

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