有 \(2n\) 个糖果,第 \(i\) 个糖果的美味值为 \(a_i\)。
在 \(n\) 天中,每天选择恰好两个糖果一起吃,一天的开心度为两个糖果美味值之和。
设 \(f(i)\) 为所有 \(\frac{(2n)!}{n!2^n}\) 种不同方案中,第 \(i\) 小的开心度之和。
对 \(i = 1 \sim n\),输出 \(f(i) \pmod 998244353\)。
\(1 \le n \le 100,1 \le a_i \le 10^9\)
称一种吃糖果的方案为一个匹配,例如对于 \(n = 2\) 的所有匹配为 \(S_1 = \{(a_1, a_2), (a_3,a_4)\}, S_2 = \{(a_1,a_3),(a_2,a_4)\},S_3=\{(a_1,a_4),(a_2,a_3)\}\)
设 \(b_i\) 为某个匹配中和是第 \(i\) 小的二元组的和,例如对于 \(\{(1, 3), (2, 6)\}\) 的 \(b_1 = 1 + 3\)
则 \(f(i)\) 为所有匹配的 \(b_i\) 的和,即 \(f(i) = \sum\limits_{b_i}b_i\)
拆贡献,\(b_i = \sum\limits_{x=1}^V[b_i\ge x]\),\(b_i \ge x\) 等价于这个匹配至少有 \(n-x+1\) 个 \(b\) 满足 \(b \ge x\)
枚举 \(x\) 求 \(b\)
设 \(F_i\) 为满足 \(i = \sum\limits_{j=1}^n[b_j\ge x]\) 的匹配的个数,则 \(\sum\limits_{j=i}^nF_j\) 可以贡献到 \(b_i\)
直接求 \(F\) 不好求。设 \(G_i\) 为钦定了 \(i\) 个 \(b\) 满足 \(b \ge x\) 的方案数,则有
根据二项式反演可得
考虑求 \(G\),将 \(a\) 升序排序。
\(a_i\) 和 \(a_j(j<i)\) 可以被钦定,当且仅当 \(a_i + a_j \ge x\) 且 \(a_j \le a_i\),即 \(x - a_i \le a_j \le a_i\),设对于 \(i\) 满足这个限制的 \(j\) 的取值范围为 \([l_i,r_i]\)。因为 \(a_i \le a_{i+1}\),所以 \([l_i,r_i]\subseteq[l_{i+1},r_{i+1}]\)
设 \(f_{i,j}\) 为考虑了 \(i\) 个糖果,有 \(j\) 对二元组满足其和 \(\ge x\) 的方案数。
选择 \(a_i\) 与前面的一个糖果:\(f_{i,j} += f_{i-1,j-1} \times (r_i - l_i + 1 - 2(j-1))\)
不选 \(a_i\):\(f_{i,j} += f_{i-1,j}\)
则 \(G_i = f_{2n,i} \times \frac{(2n - 2i)!}{(n - i)!2^{n-i}}\),表示先选 \(i\) 个二元组,剩下的随便。
以上可以在 \(O(n^2V)\) 的时间复杂度内求出每个 \(f(i)\)。
但是 \(V \le 10^9\),考虑 \(b\) 的值,因为 \(b = a_i + a_j\),则值不同的 \(b\) 只有 \(O(n^2)\) 个,将这些值作为 \(x\),再乘上出现的次数就行了,时间复杂度 \(O(n^4)\)
#define M 998244353ll
inline int MOD(ll x) { return x >= M ? x - M : x; }
inline void ADD(ll& x, ll y) { x = MOD(x + y); }bool _st;const int N = 202;
int cp, n, n2;
ll a[N], c[N * N], C[N][N], fac[N], ifac[N], pw[N], ipw[N];int l[N];
ll f[N][N], F[N], G[N], ans[N];
void solve(int x) {rep(i, 1, n2) l[i] = ::std::lower_bound(a + 1, a + 1 + n2, c[x] - a[i]) - a;memset(f, 0, sizeof(f));f[0][0] = 1;rep(i, 1, n2) rep(j, 0, n){if((j << 1) > i) break;ADD(f[i][j], f[i - 1][j]);int val = i - l[i] - 2 * (j - 1);if(j && val > 0)ADD(f[i][j], f[i - 1][j - 1] * val % M);}rep(i, 1, n) G[i] = ((f[n2][i] * fac[n2 - 2 * i]) % M * (ifac[n - i] * ipw[n - i] % M)) % M;rep(i, 1, n){F[i] = 0;rep(j, i, n)if((i - j) & 1) ADD(F[i], M - C[j][i] * G[j] % M);else ADD(F[i], C[j][i] * G[j] % M);}per(i, 1, n) ADD(F[i], F[i + 1]);rep(i, 1, n) ADD(ans[i], F[n - i + 1] * (c[x] - c[x - 1]) % M);
}bool _ed;
int main() { FIN ::std::cerr << (&_ed - &_st) / 1024.0 / 1024 << ::std::endl;Rep(i, 0, N){C[i][0] = 1;rep(j, 1, i) C[i][j] = MOD(C[i - 1][j] + C[i - 1][j - 1]);}fac[0] = pw[0] = 1;Rep(i, 1, N)fac[i] = fac[i - 1] * i % M,pw[i] = MOD(pw[i - 1] + pw[i - 1]);ifac[N - 1] = cksm<M>(fac[N - 1], M - 2);ipw[N - 1] = cksm<M>(pw[N - 1], M - 2);per(i, 0, N - 2)ifac[i] = ifac[i + 1] * (i + 1) % M,ipw[i] = MOD(ipw[i + 1] + ipw[i + 1]);qr(n);n2 = n << 1;rep(i, 1, n2) qr(a[i]);::std::sort(a + 1, a + 1 + n2);rep(i, 1, n2) rep(j, i + 1, n2) c[++cp] = a[i] + a[j];::std::sort(c + 1, c + 1 + cp);cp = ::std::unique(c + 1, c + 1 + cp) - c - 1;rep(i, 1, cp) solve(i);rep(i, 1, n) qw(ans[i]), ps;return 0;
}