Submission #53145345

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

vector<mint> prod(const vector<int> &a, int l, int r) {
    if (r - l == 1) return {1, a[l]};
    int m = (l + r) / 2;
    return convolution(prod(a, l, m), prod(a, m, r));
}
mint f[3 * 100010], fact[3 * 100010];
int main() {
    int n;
    cin >> n;

    mint sumA = 0, prodA = 1;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sumA += a[i];
        prodA *= a[i];
    }
    vector<mint> p = prod(a, 0, n);

    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = i * fact[i - 1];

    f[n] = prodA * fact[n];
    for (int m = n - 1; m >= 0; --m) {
        f[m] = fact[m] * p[m] + f[m + 1] / (sumA - m);
    }
    cout << f[0].val() << endl;
}

Submission Info

Judge Result