AGC054B

MurataHimeko · 2023-07-07 10:31:44 · 题解

一个排列肯定只对应一个拿数的情况。

对排列计数是困难的，不妨对拿数的情况计数。

如果我们已经确定了 A,B 拿到的数以及拿数顺序，那么可以唯一确定一个排列。

发现需要“拿到的数的个数”这个信息。

设 f_{i,j,k} 表示，到了第 i 个数，A 拿到的数的和为 j，A 已经拿了 k 个数的方案数。

最后答案为 \sum_{i} f_{n,\frac{sum}{2}, i} \times i!\times (n-i)!。

代码：

const int mod = 998244353;
int n, a[105];
int f[105][10005], g[105][10005];
int fac[105];

int main () {
    io >> n;
    re(i, n) io >> a[i];
    int sum = 0;
    g[0][0] = 1;
    re(i, n) {
        sum += a[i];
        rep(j, 0, i) {
            rep(k, 0, sum) {
                f[j][k] = g[j][k];
                if(k >= a[i] && j) f[j][k] = (f[j][k] + g[j-1][k - a[i]]) % mod;
            }
        }
        rep(j, 0, i) rep(k, 0, sum) g[j][k] = f[j][k], f[j][k] = 0;
    }
    fac[0] = 1;
    re(i, n) fac[i] = 1ll * fac[i-1] * i % mod;
    ll ans = 0;
    if(sum & 1) {
        io << "0";
        return 0;
    }
    re(i, n) {
        ans = (ans + 1ll * g[i][sum / 2] * fac[i] % mod * fac[n-i] % mod) % mod;
    }
    io << ans;
}