Official Analysis (C++)

Explanation

Let's consider our first round, where we have $n$ players and no damage has been dealt so far. Then, after this first round, any player with health in the range $[1, n-1]$ will be killed. In general, if we have $i$ heroes, and $j$ damage has been dealt so far, then any hero with health in the range $[j + 1, j + i - 1]$ will be killed in this round.

Notice that the ranges of health values that get killed in each around are disjoint. This indicates that we should do our counting based on the results from each round.

The only thing that affects which range of values gets killed in a round are the number of heroes $i$ that are alive, and the damage $j$. Instead of thinking from the perspective of assigning health to the heroes currently alive, we instead assign health to the heroes that die, as the round that a hero dies in directly maps to a range of possible health values.

With this approach in mind, let's formulate a DP state $\texttt{dp}[i][j]$, which equals the number of ways we can assign health to the heroes that were killed, if $i$ of them are still alive and a total of $j$ damage has been dealt to all the heroes. Then, we have to consider three separate cases for the outcome of a round.

If no hero dies, we still need to consider this as a round that has been completed. Thus, we perform the following transition:

If some, but not all heroes die, then we know that the heroes who died had health values in the range $[j + 1, j + i - 1]$. Also, we have to choose which heroes out of the $i$ heroes currently alive will die. Let $k$ be the new number of heroes after this round. Then, we have the following transition:

Lastly, if all the heros die, then we handle the transition in the exact same way as the previous one.

Implementation

Time Complexity: $\mathcal{O}(N^2 X)$

Copy
#include <bits/stdc++.h>

using ll = long long;

 Code Snippet: Binary Exponentiation (from the module) (Click to expand)

constexpr int MOD = 998244353;

int main() {
	int n, x;