E. Arena

假设$dp[n][x]\{dp[n][x]\}$为有$n\{n\}$个人活着，每个人的体力值范围为$1\sim x\{1\backslash sim\; x\}$的方案数。

考虑以下几种情况：

当$n==2\{n==2\}$时，只有两个人的体力值相同时才满足条件，$dp[n][x]=x\{dp[n][x]=x\}$

当$n>x\{n>x\}$时，所有的情况都满足条件，所有的人都会在第一回合结束后死亡，$dp[n][x]=x^n\{dp[n][x]=x^n\}$

当$n\le x\{n\backslash le\; x\}$时，先考虑第一回合后还有人存活的情况，假设第一回合结束后有$i\{i\}$个人死亡，为保证不能有赢家$i\mathrm{\ne }n-1\{i\backslash neq\; n-1\}$，选择死亡的人的方案有${\displaystyle \left(\genfrac{}{}{0px}{}{n}{i}\right)}\{\backslash displaystyle\; \backslash binom\{n\}\{i\}\}$，死亡的人体力安排方案数为$(n-1{)}^i\{(n-1)^i\}$，活着的人的体力安排安排方案数为$dp[n-i][x-(n-1)]\{dp[n-i][x-(n-1)]\}$。显然，第一回合结束后有$n\{n\}$个人死亡时，方案数为$dp[n][n-1]\{dp[n][n-1]\}$

故状态转移方程为：

$dp[n][x]=\{\begin{array}{c}x,n==2\\ x^n,n>x\\ dp[n][n-1]+{\sum }_{i=0}^{n-2}{\displaystyle \left(\genfrac{}{}{0px}{}{n}{i}\right)(n-1{)}^{i}dp[n-i][x-(n-1)],n\le x}\end{array}\{\; dp[n][x]=\backslash begin\{cases\}x,n==2\backslash \backslash \; x^n,n>x\backslash \backslash \; dp[n][n-1]+\backslash sum\_\{i=0\}^\{n-2\}\backslash displaystyle\; \backslash binom\{n\}\{i\}\; (n-1)^i\; dp[n-i][x-(n-1)],n\backslash le\; x\; \backslash end\{cases\}\; \}$

code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=505,mod=998244353 ;
ll c[maxn][maxn],f[maxn][maxn];
ll qpow(ll a,int b) {
	ll res(1);
	while(b) {
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int main() {
	cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
	int n,x;
	c[0][0]=1;
	for(int i=1;i<=500;++i) {
		c[i][0]=1;
		for(int j=1;j<=i;++j) {
			c[i][j]=c[i-1][j]+c[i-1][j-1];
			if(c[i][j]>=mod) c[i][j]-=mod;
		}
	}
	for(int i=1;i<=500;++i) f[2][i]=i;
	for(int i=3;i<=500;++i) {
		for(int j=1;j<i;++j) f[i][j]=qpow(j,i);
		for(int j=i;j<=500;++j) {
			for(int k=i-2;~k;--k) {
				f[i][j]=(c[i][k]*qpow(i-1,k)%mod*f[i-k][j-(i-1)]+f[i][j])%mod;
			}
			f[i][j]+=f[i][i-1];
			if(f[i][j]>=mod) f[i][j]-=mod;
		}
	}
	cin>>n>>x;
	cout<<f[n][x]<<'\n';
	return 0;
}