Submission #72067525

---

Source Code Expand

#include<cstdio>
int n;
const int mod = 998244353;
long long int fct[3000];
long long int ifct[3000];
long long int f[55];
long long int dp[3000][55];
long long int sdp[55][55][55];
long long int mpow(long long int x, int y) {
	if (y == 0)return 1;
	long long int r = mpow(x, y / 2);
	r *= r;
	r %= mod;
	if (y % 2 == 1) {
		r *= x;
		r %= mod;
	}
	return r;
}
long long int minv(long long int x) {
	return mpow(x, mod - 2);
}
int main() {
	scanf("%d", &n);
	fct[0] = 1;
	ifct[0] = 1;
	for (int i = 1; i <= n * n; i++) {
		fct[i] = fct[i - 1] * i;
		fct[i] %= mod;
		ifct[i] = minv(fct[i]);
	}
	long long int pown = 1;
	for (int i = 0; i < n; i++) {
		pown *= n;
		pown %= mod;
	}
	sdp[0][0][n] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				int p = j;
				if (k > j) {
					p = k;
				}
				for (int ii = k; ii <= n; ii++) {
					sdp[i + 1][p][ii - k] += sdp[i][j][ii] * fct[ii] % mod * ifct[k] % mod * ifct[ii - k] % mod;
					sdp[i + 1][p][ii - k] %= mod;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		f[i - 1] = sdp[n][i][0];
	}
	long long int ans = 0;
	dp[0][0] = 1;
	for (int i = 0; i < n * n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k + j < n; k++) {
				dp[i + 1][j + k] += f[k] * dp[i][j] % mod;
				dp[i + 1][j + k] %= mod;
			}
		}
	}
	for (int j = 0; j < n; j++) {
		ans += dp[n * n][j];
		ans %= mod;
	}
	printf("%lld\n", ans);
	return 0;
}

Submission Info

Judge Result