思路
首先不难发现一个规律，当 \(sum\) 为奇数时不可能有解。
定义 \(dp_{i,j,k,0/1}\) 表示 A 在前 \(i\) 个数中选出和为 \(j\) 的 \(k\) 个数，且第 \(i\) 个 不选/选 的方案数。
那么，我们只需要对于第 \(i\) 个数的状态分类讨论就能得到状态转移方程：
- 不选 \(i\)，\(dp_{i,j,k,0} = dp_{i - 1,j,k,0/1}\)。
- 选 \(i\)，\(dp_{i,j,k,1} = dp_{i - 1,j - a_i,k - 1,0/1}\)。
综上，得到状态转移方程：
\[ \left\{\begin{matrix} dp_{i,j,k,0} = dp_{i - 1,j,k,0/1}\\ dp_{i,j,k,1} = dp_{i - 1,j - a_i,k - 1,0/1} \end{matrix}\right. \]然后，我们就得到了序列 \(a\) 固定时的答案。那么，我们还要考虑一下 \(a\) 不固定的情况。
假设 A 最后取出了 \(x\) 个数，那么，我们就可以就可以对 A 和 B 两人选取数的序列进行全排列，即 \((x!)((n - i)!)\)。
现在还有一个问题，为什么不能直接对 \(a\) 进行全排列，也就是直接乘 \(n!\)。那是因为如果 A 和 B 两人选取的序列是固定的，由于题目中的条件当前权值小的人才能取数，所以说当两人选取数字的序列固定了，那么，拼起来的序列 \(a\) 也是固定的。
综上，答案为 \(\sum_{i = 1}^{n - 1}(dp_{n,\frac{sum}{2},i,0/1} \times (i!) \times ((n - i)!))\)。
这样就可以得到 MLE 1 个点 的代码。
然后，我们发现 \(dp_i\) 时的所有状态都是由 \(dp_{i - 1}\) 转移来的，所以说直接滚动一下即可。
Code
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 110,M = 1e4 + 10,mod = 998244353;
int n,r,sum,ans;
int arr[N],mul[N];
int dp[2][M][N][2];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline void init(){
mul[0] = 1;
for (re int i = 1;i <= n;i++) mul[i] = mul[i - 1] * i % mod;
}
signed main(){
n = read();
init();
for (re int i = 1;i <= n;i++){
arr[i] = read();
sum += arr[i];
}
if (sum & 1){
puts("0");
return 0;
}
dp[0][0][0][0] = dp[0][arr[1]][1][1] = 1;
for (re int i = 2;i <= n;i++){
r ^= 1;
for (re int j = 0;j <= sum;j++){
for (re int k = 0;k <= i;k++) dp[r][j][k][0] = dp[r][j][k][1] = 0;
}
for (re int j = 0;j <= sum;j++){
for (re int k = 0;k <= i;k++){
dp[r][j][k][0] = (dp[r ^ 1][j][k][0] + dp[r ^ 1][j][k][1]) % mod;
if (j >= arr[i]) dp[r][j][k][1] = (dp[r ^ 1][j - arr[i]][k - 1][0] + dp[r ^ 1][j - arr[i]][k - 1][1]) % mod;
}
}
}
for (re int i = 1;i < n;i++) ans = (ans + (dp[r][sum / 2][i][0] + dp[r][sum / 2][i][1]) % mod * mul[i] % mod * mul[n - i] % mod) % mod;
printf("%lld",ans);
return 0;
}