题解

思路

观察第一回合。若当前有 $i$ 个英雄，则每人受到 $i-1$ 点伤害。生命值不超过 $i-1$ 的英雄死亡，其余英雄的剩余生命值恰好落在一个更小的连续值域内，因此问题具有递归结构。

做法

令 $f[i][j]$ 表示 $i$ 个英雄、初始生命值均在 $[1,j]$ 时没有胜者的方案数。

若 $j\le i-1$，所有英雄第一回合同时死亡，所以 $f[i][j]=j^i$。

否则第一回合后设有 $s$ 个英雄存活。死亡者各有 $i-1$ 种生命值选择，存活者减去 $i-1$ 后形成一个上界为 $j-(i-1)$ 的同类问题。$s=1$ 会产生胜者，不能计入；$s=0$ 以及 $2\le s\le i$ 可以计入：

$$f[i][j]=(i-1)^i+\sum_{s=2}^{i}\binom{i}{s}(i-1)^{i-s}f[s][j-i+1].$$

按 $i$ 从小到大、$j$ 从小到大计算。求和中 $s<i$ 的行已经完成，$s=i$ 时使用的是同一行更小的第二维，依赖无环。

子任务一可枚举所有 $x^n$ 个生命值数组并直接模拟；子任务二中两个英雄没有胜者当且仅当生命值相等，答案为 $x$。

复杂度

预处理组合数和幂后，动态规划时间复杂度为 $O(n^2x)$，空间复杂度为 $O(nx)$。