Arena

Análisis oficial (C++) 

Explicación

Consideremos nuestra primera ronda, donde tenemos $n$ jugadores y aún no se ha infligido daño. Entonces, después de esta primera ronda, cualquier jugador con salud en el rango $[1, n-1]$ será eliminado. En general, si tenemos $i$ héroes, y se infligió $j$ de daño hasta ahora, entonces cualquier héroe con salud en el rango $[j + 1, j + i - 1]$ será eliminado en esta ronda.

Nótese que los rangos de valores de salud que se eliminan en cada ronda son disjuntos. Esto indica que deberíamos hacer nuestro conteo basándonos en los resultados de cada ronda.

Lo único que afecta qué rango de valores se elimina en una ronda es el número de héroes $i$ que están vivos, y el daño $j$. En lugar de pensar desde la perspectiva de asignar salud a los héroes actualmente vivos, en cambio asignamos salud a los héroes que mueren, ya que la ronda en la que muere un héroe se corresponde directamente con un rango de valores de salud posibles.

Con este enfoque en mente, formulemos un estado de DP $\texttt{dp}[i][j]$, que es igual al número de formas en que podemos asignar salud a los héroes que fueron eliminados, si $i$ de ellos siguen vivos y se infligió un total de $j$ de daño a todos los héroes. Entonces, hay que considerar tres casos separados para el resultado de una ronda.

Si ningún héroe muere, igual hay que considerar esto como una ronda que se completó. Así, hacemos la siguiente transición:

Si algunos, pero no todos, los héroes mueren, entonces sabemos que los héroes que murieron tenían valores de salud en el rango $[j + 1, j + i - 1]$. Además, hay que elegir cuáles héroes de los $i$ héroes actualmente vivos morirán. Sea $k$ el nuevo número de héroes después de esta ronda. Entonces, tenemos la siguiente transición:

Por último, si todos los héroes mueren, entonces manejamos la transición exactamente de la misma forma que la anterior.

Implementación

Complejidad temporal: $\mathcal{O}(N^2 X)$

#include <bits/stdc++.h>
 
using ll = long long;
 
// BeginCodeSnip{Binary Exponentiation (from the module)}
ll exp(ll x, ll n, ll m) {
	assert(n >= 0);
	x %= m;  // nota: m * m debe ser menor que 2^63 para evitar overflow de ll
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}
// EndCodeSnip
 
constexpr int MOD = 998244353;
 
int main() {
	int n, x;
	std::cin >> n >> x;
 
	// calculamos los coeficientes binomiales con DP
	std::vector nck(n + 1, std::vector<ll>(n + 1));
	for (int i = 0; i <= n; i++) {
		nck[i][0] = nck[i][i] = 1;
		for (int j = 1; j < i; j++) {
			nck[i][j] = (nck[i - 1][j - 1] + nck[i - 1][j]) % MOD;
		}
	}
 
	/*
	 * dp[i][j] = # de asignaciones si i héroes siguen vivos y se infligió x daño
	 * Nota: solo asignamos vida a los héroes que ya murieron
	 */
	std::vector dp(n + 1, std::vector<ll>(x));
	dp[n][0] = 1;
 
	ll res = 0;
	for (int i = n; i >= 2; i--) {
		for (int j = 0; j < x; j++) {
			/*
			 * Nuestra transición ocurre cuando sucede una ronda. Notar que
			 * los rangos de valores de vida eliminados son disjuntos, por eso funciona.
			 */
 
			// transición para el caso en que todos los héroes mueren esta ronda
			int pick = std::min(x - j, i - 1);
			res += dp[i][j] * exp(pick, i, MOD);
			res %= MOD;
 
			int dmg = j + (i - 1);
			if (dmg >= x) continue;
 
			// transición si nadie muere esta ronda
			dp[i][dmg] += dp[i][j];
			dp[i][dmg] %= MOD;
 
			for (int k = i - 1; k >= 2; k--) {
				// iteramos sobre el número de héroes que matamos esta ronda
				int num_del = i - k;
				ll ways = nck[i][num_del] * exp(pick, num_del, MOD) % MOD;
				dp[k][dmg] += dp[i][j] * ways;
				dp[k][dmg] %= MOD;
			}
		}
	}
 
	std::cout << res << std::endl;
}