TLE on #35
查看原帖
TLE on #35
398152
MinimumSpanningTree最小生成树楼主2024/7/14 19:43
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
const int N=510;
ll n,x,dp[N][N],c[N][N],ans;
ll quick_pow(ll a,ll b)
{
	ll sum=1;
	while(b)
	{
		if(b%2==1) b--,sum=(sum*a)%MOD;
		a=(a*a)%MOD,b/=2;
	}
	return sum;
}
int main()
{
	scanf("%lld%lld",&n,&x);
	for(int i=0;i<=n;i++)
	{
		c[i][0]=1;
		for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
	}
	for(ll i=2;i<=n;i++) 
	{
		for(ll j=1;j<=x;j++)
		{
			if(i-1>=j) dp[i][j]=(quick_pow(j,i)+MOD-quick_pow(j-1,i))%MOD;
			else
			{
				for(int k=1;k<=i;k++) dp[i][j]=(dp[i][j]+(((dp[k][j-(i-1)]*c[i][k])%MOD)*quick_pow(i-1,i-k))%MOD)%MOD;
			}
		}
	}
	for(int i=1;i<=x;i++) ans=(ans+dp[n][i])%MOD;
	printf("%lld",ans);
	return 0;
}
2024/7/14 19:43
加载中...