题目

题目链接

题目大意

给定长度为 $n$ 的数组 $a_i$, 对于 $1 \sim n$ 的所有的排列 $p_i$, 求

$\frac{\sum\left(\left(\left( a_{p_1} +1\right) \times a_{p_{2}}+\cdots\right)\times a_{p_{n-1}}+1\right) \times a_{p_{n}}}{n !}$

解题思路

把分子展开后有

$v a l=\prod_{i=1}^{n} a_{p_i}+\prod_{i=2}^{n} a_{p_i}+\cdots+\prod_{i=n}^{n} a_{p_i}$

对于该式子的每一项，我们考虑如何算出贡献，假设当前项的长度为 $k$, 那么贡献为

$\frac{\sum\limits_{S \subseteq\{1,2, \cdots, n\},|S|=k} k ! \prod\nolimits_{i \in S} a_{i} }{\binom{n}{k} k !} = \frac{\sum\limits_{S \subseteq\{1,2, \cdots, n\},|S|=k} \prod\nolimits_{i \in S} a_{i}}{\binom{n}{k}}$

其中，分子等价于 $\prod\limits_{i=1}^{n}\left(1+a_i x\right)$ 中 $x^k$ 的系数, 不妨设为 $f(k)$, 那么最终的期望为

$E(x)=\frac{\sum\limits_{i=1}^{n} f(i) \times i ! \times(n-i) !}{n !}$

显然，$f$ 可以通过分治$FFT$ 求解

完整代码

#include <bits/stdc++.h>
using namespace std;

const int G = 3;
const int maxn = 2e5 + 5;
const int mod = 998244353;

int R[maxn];

int qpow(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1LL * a * a % mod)
        if (b & 1) res = 1LL * res * a % mod;
    return res;
}

void NTT(int limit, int *A, int type) {
    for (int i = 0; i < limit; i++)
        if (i < R[i]) swap(A[i], A[R[i]]);
    for (int mid = 1; mid < limit; mid <<= 1) {
        int wn = qpow(G, (mod - 1) / (mid << 1));
        for (int pos = 0; pos < limit; pos += (mid << 1)) {
            int w = 1;
            for (int k = 0; k < mid; k++, w = 1LL * w * wn % mod) {
                int x = A[pos + k], y = 1LL * w * A[pos + mid + k] % mod;
                A[pos + k] = (x + y) % mod;
                A[pos + k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if (type == 1) return;
    for (int i = 1; i < limit / 2; i++) swap(A[i], A[limit - i]);
    int inv = qpow(limit, mod - 2);
    for (int i = 0; i < limit; i++) {
        A[i] = 1LL * A[i] * inv % mod;
    }
}

void mulNTT(int *f, int *g, int *h, int n, int m) {
    int limit = 1, L = 0;
    while (limit <= n + m) limit <<= 1, L++;

    for (int i = n + 1; i < limit; ++i) f[i] = 0;
    for (int i = m + 1; i < limit; ++i) g[i] = 0;

    for (int i = 0; i < limit; ++i)
        R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));

    NTT(limit, f, 1), NTT(limit, g, 1);
    for (int i = 0; i < limit; ++i) h[i] = 1LL * f[i] * g[i] % mod;
    NTT(limit, h, -1);
}

int a[maxn], f[maxn], g[maxn], h[maxn];
int inv[maxn], fact[maxn], infact[maxn];

void init() {
    inv[0] = inv[1] = 1;
    for (int i = 2; i < maxn; i++)
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    fact[0] = infact[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
        infact[i] = 1LL * infact[i - 1] * inv[i] % mod;
    }
}

vector<int> solve(int l, int r) {
    if (l == r) return {1, a[l]};
    int mid = (l + r) >> 1;
    int len1 = mid - l + 1, len2 = r - mid;
    auto res1 = solve(l, mid);
    auto res2 = solve(mid + 1, r);
    for (int i = 0; i <= len1; i++) f[i] = res1[i];
    for (int i = 0; i <= len2; i++) g[i] = res2[i];
    mulNTT(f, g, h, len1, len2);

    vector<int> res;
    res.resize(len1 + len2 + 1);
    for (int i = 0; i <= len1 + len2; i++) res[i] = h[i];
    return res;
}

void Main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    auto res = solve(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += 1LL * res[i] * fact[i] % mod * fact[n - i] % mod;
        if (ans >= mod) ans -= mod;
    }
    ans = 1LL * ans * infact[n] % mod;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    init();
    int T;
    cin >> T;
    while (T--) Main();
    return 0;
}