Round I · PRIOR
Sample Problem
Representative of the style and difficulty you can expect in Round I.
Expected Inversions Dice DP
Problem Statement
Alice is hosting a tournament with N independent bots. Each bot plays a mini-game to determine its final score.
The mini-game works as follows: Each bot starts with a score of 0. They are given a special M-sided die, where the faces have integer values A1, A2, …, AM. The bot rolls the die exactly K times and adds the results of the rolls to its score. All rolls are independent, and each face has an equal probability of 1/M of appearing on any given roll.
After all N bots have finished their K rolls, their final scores are placed into an array S = [S1, S2, …, SN].
An inversion in the array S is defined as a pair of indices (i, j) such that 1 ≤ i < j ≤ N and Si > Sj.
Find the expected number of inversions in the array S. Because this expected value can be a rational number, output it modulo 998244353.
Input
The first line contains three integers N, K, and M (2 ≤ N ≤ 109, 1 ≤ K ≤ 105, 1 ≤ M ≤ 100) — the number of bots, the number of rolls each bot makes, and the number of faces on the die.
The second line contains M integers A1, A2, …, AM (1 ≤ Ai ≤ 20) — the values on the faces of the die.
Output
Print a single integer — the expected number of inversions modulo 998244353.