The 2023 ICPC Asia Hefei Regional Contest

目录

B. Queue Sorting

应该还会再补几题

B. Queue Sorting

题解：

Dilworth定理:

【偏序关系与偏序集、Hasse图、极大元、极小元、全序关系、最大元、良序集/三小时讲不完离散数学之集合论/考研复试/期末复习考前冲刺/近世代数/抽象代数】https://www.bilibili.com/video/BV1FK4y1i7FP?vd_source=8dcdcdf1464ff87d2684660b142a2bfe

偏序集-Dilworth定理_偏序集的例子-CSDN博客

#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
const int inf = 0x3f3f3f3f3f3f3f3f, N = 1e5 + 5, mod = 998244353;
class modint {
public:
	int x;
	modint(int o = 0) { o %= mod; x = o >= 0 ? o : mod + o; }
	modint& operator = (int o) { o %= mod; return  x = o >= 0 ? o : mod + o, *this; }
	modint& operator +=(modint o) { return x = x + o.x >= mod ? x + o.x - mod : x + o.x, *this; }
	modint& operator -=(modint o) { return x = x - o.x < 0 ? x - o.x + mod : x - o.x, * this; }
	modint& operator *=(modint o) { return x = x * o.x % mod, *this; }
	modint& operator ^=(int b) {
		modint a = *this, c = 1;
		for (; b; b >>= 1, a *= a)if (b & 1)c *= a;
		return x = c.x, *this;
	}
	modint& operator /=(modint o) { return *this *= o ^= mod - 2; }
	friend modint operator +(modint a, modint b) { return a += b; }
	friend modint operator -(modint a, modint b) { return a -= b; }
	friend modint operator *(modint a, modint b) { return a *= b; }
	friend modint operator /(modint a, modint b) { return a /= b; }
	friend modint operator ^(modint a, int b) { return a ^= b; }
	friend bool operator ==(modint a, int b) { return a.x == b; }
	friend bool operator !=(modint a, int b) { return a.x != b; }
	bool operator ! () { return !x; }
	modint operator - () { return x ? mod - x : 0; }
	bool operator <(const modint& b)const { return x < b.x; }
	bool operator >(const modint& b)const { return x > b.x; }
};
inline modint qpow(modint x, int y) { return x ^ y; }
int fpow(int x, int r)
{
	int result = 1;
	while (r)
	{
		if (r & 1)result = result * x % mod;
		r >>= 1;
		x = x * x % mod;
	}
	return result;
}
 
namespace binom {
	int fac[N], ifac[N];
	int __ = []
	{
		fac[0] = 1;
		for (int i = 1; i <= N - 5; i++)
			fac[i] = fac[i - 1] * i % mod;
		ifac[N - 5] = fpow(fac[N - 5], mod - 2);
		for (int i = N - 5; i; i--)
			ifac[i - 1] = ifac[i] * i % mod;
		return 0;
	}();
 
	inline int C(int n, int m)
	{
		if (n < m || m < 0)return 0;
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
 
	inline int A(int n, int m)
	{
		if (n < m || m < 0)return 0;
		return fac[n] * ifac[n - m] % mod;
	}
}
using namespace binom;
void add(int& x, const int& y) {
	(x += y) %= mod;
}
signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector<int>a(n + 1), pre(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	vector<vector<modint>>dp(n + 1, vector<modint>(pre[n] + 2));
	dp[1][pre[1] + 1] = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= pre[i] + 1; j++) {
			for (int x = 0; x < a[i + 1]; x++) {
				for (int k = 1; k < j; k++) {
					dp[i + 1][x + k + 1] += dp[i][j] * C(j - k + a[i + 1] - x - 2, a[i + 1] - x - 1);
				}
			}
			dp[i + 1][a[i + 1] + j] += dp[i][j];
		}
	}
	modint ans = 0;
	for (int i = 1; i <= pre[n]+1; i++) {
		ans += dp[n][i];
	}
	cout << ans.x << "\n";
 
}