Submission #53158065

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

namespace Polynomial {
    const int Mod = 998244353;
    const int G = 3;
    
    template<int mod>
    class Modint {
        private:
            unsigned int x;
        public:
            Modint() = default;
            Modint(unsigned int x): x(x) {}
        friend istream& operator >> (istream& in, Modint& a) {return in >> a.x;}
        friend ostream& operator << (ostream& out, Modint a) {return out << a.x;}
        friend Modint operator + (Modint a, Modint b) {return (a.x + b.x) % mod;}
        friend Modint operator - (Modint a, Modint b) {return (a.x - b.x + mod) % mod;}
        friend Modint operator * (Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
        friend Modint operator / (Modint a, Modint b) {return a * ~b;}
        friend Modint operator ^ (Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
        friend Modint operator ~ (Modint a) {return a ^ (mod - 2);}
        friend Modint operator - (Modint a) {return (mod - a.x) % mod;}
        friend Modint& operator += (Modint& a, Modint b) {return a = a + b;}
        friend Modint& operator -= (Modint& a, Modint b) {return a = a - b;}
        friend Modint& operator *= (Modint& a, Modint b) {return a = a * b;}
        friend Modint& operator /= (Modint& a, Modint b) {return a = a / b;}
        friend Modint& operator ^= (Modint& a, int b) {return a = a ^ b;}
        friend Modint& operator ++ (Modint& a) {return a += 1;}
        friend Modint operator ++ (Modint& a, int) {Modint x = a; a += 1; return x;}
        friend Modint& operator -- (Modint& a) {return a -= 1;}
        friend Modint operator -- (Modint& a, int) {Modint x = a; a -= 1; return x;}
        friend bool operator == (Modint a, Modint b) {return a.x == b.x;}
        friend bool operator != (Modint a, Modint b) {return !(a == b);}
    };
    typedef Modint<Mod> mint;

    void init_convo(vector<int>& rev, int& lim, int n, int m) {
        int s = 0;
        for (lim = 1; lim <= n + m; lim <<= 1, s++);
        rev.resize(lim);
        for (int i = 0; i < lim; i++) {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (s - 1));
        }
    }

    void NTT(vector<mint>& f, vector<int>& rev, int lim, int type) {
        f.resize(lim, 0);
        for (int i = 0; i < lim; i++) {
            if (i < rev[i]) {
                swap(f[i], f[rev[i]]);
            }
        }
        for (int i = 1; i < lim; i <<= 1) {
            mint mul = (mint)G ^ ((Mod - 1) / (i << 1));
            if (type == -1) {
                mul = ~mul;
            }
            for (int j = 0; j < lim; j += (i << 1)) {
                mint w = 1;
                for (int k = 0; k < i; k++, w *= mul) {
                    mint x = f[j + k], y = w * f[j + k + i];
                    f[j + k] = x + y;
                    f[j + k + i] = x - y;
                }
            }
        }
    }

    vector<mint> convolution(vector<mint> f, vector<mint> g, int k1, int k2, mint (*calc)(mint x, mint y)) {
        int n = SZ(f) - 1, m = SZ(g) - 1, lim;
        vector<int> rev;
        init_convo(rev, lim, k1 * n, k2 * m);

        NTT(f, rev, lim, 1);
        NTT(g, rev, lim, 1);
        vector<mint> h(lim);
        for (int i = 0; i < lim; i++) {
            h[i] = calc(f[i], g[i]);
        }
        NTT(h, rev, lim, -1);
        mint invlim = ~(mint)lim;
        for (int i = 0; i < lim; i++) {
            h[i] = h[i] * invlim;
        }
        h.resize(k1 * n + k2 * m + 1);
        return h;
    }
    vector<mint> convolution(const vector<mint>& f, const vector<mint>& g) {
        return convolution(f, g, 1, 1, [](mint x, mint y) -> mint {
            return x * y;
        });
    }

    vector<mint> derivation(vector<mint> f) {
        int n = SZ(f);
        for (int i = 1; i < n; i++) {
            f[i - 1] = f[i] * i;
        }
        f.resize(n - 1);
        return f;
    }
    vector<mint> integrate(vector<mint> f) {
        int n = SZ(f);
        f.resize(n + 1, 0);
        for (int i = n - 1; i >= 0; i--) {
            f[i + 1] = f[i] / (i + 1);
        }
        f[0] = 0;
        return f;
    }

    vector<mint> polyadd(const vector<mint>& f, const vector<mint>& g) {
        int n = SZ(f), m = SZ(g);
        int mx = max(n, m), mn = min(n, m);
        vector<mint> h(mx);
        for (int i = 0; i < mn; i++) {
            h[i] = f[i] + g[i];
        }
        for (int i = mn; i < mx; i++) {
            h[i] = (n > m) ? f[i] : g[i];
        }
        return h;
    }
    vector<mint> polysub(const vector<mint>& f, const vector<mint>& g) {
        int n = SZ(f), m = SZ(g);
        int mx = max(n, m), mn = min(n, m);
        vector<mint> h(mx);
        for (int i = 0; i < mn; i++) {
            h[i] = f[i] - g[i];
        }
        for (int i = mn; i < mx; i++) {
            h[i] = (n > m) ? f[i] : -g[i];
        }
        return h;
    }

    vector<mint> polyinv(vector<mint> f, int n) {   // 1 / f(x) (mod x^n)
        f.resize(n);
        if (n == 1) {
            f[0] = ~f[0];
            return f;
        }
        auto g = polyinv(f, (n + 1) >> 1);
        g = convolution(f, g, 1, 2, [](mint x, mint y) -> mint {
            return (2 - x * y) * y;
        });
        g.resize(n, 0);
        return g;
    }

    vector<mint> polyln(vector<mint> f, int n) {    // ln f(x) (mod x^n) , f[0] = 1
        f = integrate(convolution(derivation(f), polyinv(f, n)));
        f.resize(n, 0);
        return f;
    }

    vector<mint> polyexp(vector<mint> f, int n) {   // exp f(x) (mod x^n) , f[0] = 0 | Newton's Method
        f.resize(n, 0);
        if (n == 1) {
            f[0] = 1;
            return f;
        }
        auto g0 = polyexp(f, (n + 1) >> 1);
        auto g1 = polysub(polyln(g0, n), f);
        auto h = convolution(g0, g1, 1, 1, [](mint x, mint y) -> mint {
            return x * (1 - y);
        });
        h.resize(n, 0);
        return h;
    }

    vector<mint> __polyksm(vector<mint> f, int k, int n) {    // [f(x)]^{k} (mod x^n) , f[0] = 0 | exp(ln f(x))
        f = polyln(f, n);
        for (int i = 0; i < n; i++) {
            f[i] *= k;
        }
        f = polyexp(f, n);
        f.resize(n, 0);
        return f;
    }

    vector<mint> polyksm(vector<mint> f, int k, int n) {    // [f(x)]^{k} (mod x^n)
        f.resize(n, 0);
        int p = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] != 0) {
                p = i;
                break;
            }
        }
        mint coef = ~f[p];
        vector<mint> g(n - p);
        for (int i = 0; i < n - p; i++) {
            g[i] = f[i + p] * coef;
        }
        g = __polyksm(g, k, n);
        
        ll d = 1ll * p * k;
        coef = (~coef) ^ k;
        fill(f.begin(), f.end(), 0);
        for (int i = n - 1; i >= d; i--) {
            f[i] = g[i - d] * coef;
        }
        return f;
    }
}
using Polynomial::convolution;
using Polynomial::Mod;
using Polynomial::mint;

vector<mint> dc(int l, int r, vector<int>& a) {
    if (l == r) {
        vector<mint> res(2);
        res[0] = 1; res[1] = a[l];
        return res;
    }
    int mid = (l + r) >> 1;
    auto L = dc(l, mid, a);
    auto R = dc(mid + 1, r, a);
    auto res = convolution(L, R);
    return res;
}

void solve() {
    int n;
    cin >> n;
    vector a(n + 1, 0);
    mint tot = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        tot += a[i];
    }

    auto g = dc(1, n, a);
    assert(SZ(g) == n + 1);
    g.push_back(0);
    vector f(n + 2, (mint)0);
    mint coef = 1; f[0] = 1;
    for (int i = 1; i <= n + 1; i++) {
        coef *= (mint)i * ~(tot - (i - 1));
        f[i] = g[i] * coef;
    }

    mint ans = 0;
    for (int i = 0; i <= n; i++) {
        ans += (f[i] - f[i + 1]) * (i + 1);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}

Submission Info

Judge Result