提出 #43027869

---

ソースコード 拡げる

// LUOGU_RID: 113480517
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 510, MOD = 998244353;
int n, s[N], f[N][N][N], C[N][N];
void add(int &x, int y) {
	if ((x += y) >= MOD) x -= MOD;
}
signed main() {
	read(n);
	F(i, 1, n) {
		int x; read(x);
		s[x]++;
	}
	F(i, 0, n) {
		C[i][0] = 1;
		F(j, 1, i) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
	}
	DF(i, n, 1) s[i] += s[i + 1];
	f[n + 1][0][0] = 1;
	DF(i, n, 1)
		F(j, 0, n / (i + 1))
			F(k, j * (i + 1), n)
				if (f[i + 1][j][k]) {
					// cout << "! " << i + 1 << " " << j << " " << k << " " << f[i + 1][j][k] << endl;
					int t = 1;
					F(l, 0, min(s[i] - j, (s[i] - k) / i)) {
						// if (i == 2 && j + l == 2) {
						// 	cout << C[s[i] - j][l] << " " << s[i] << " " << k << " " << i * l << " " << C[s[i] - k][i * l] << endl;
						// }
						add(f[i][j + l][k + i * l], (ll) f[i + 1][j][k] * C[s[i] - j][l] % MOD * t % MOD);
						t = (ll) t * C[s[i] - k - l * i][i] % MOD;
					}
				}
	int ans = 0;
	F(i, 1, n) add(ans, f[1][i][n]);
	cout << ans;
	return 0;
}

提出情報

ジャッジ結果