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

考虑以下几种情况:

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

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

nx{n\le x}时,先考虑第一回合后还有人存活的情况,假设第一回合结束后有i{i}个人死亡,为保证不能有赢家in1{i\neq n-1},选择死亡的人的方案有(ni){\displaystyle \binom{n}{i}},死亡的人体力安排方案数为(n1)i{(n-1)^i},活着的人的体力安排安排方案数为dp[ni][x(n1)]{dp[n-i][x-(n-1)]}。显然,第一回合结束后有n{n}个人死亡时,方案数为dp[n][n1]{dp[n][n-1]}

故状态转移方程为:

dp[n][x]={x,n==2xn,n>xdp[n][n1]+i=0n2(ni)(n1)idp[ni][x(n1)],nx{ dp[n][x]=\begin{cases}x,n==2\\ x^n,n>x\\ dp[n][n-1]+\sum_{i=0}^{n-2}\displaystyle \binom{n}{i} (n-1)^i dp[n-i][x-(n-1)],n\le x \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;
}