本文共 1142 字，大约阅读时间需要 3 分钟。

题意：

有n个点，每个点对应一个权值，现在要建一颗树，给第 i 个点从点[0, i - 1]中随机选择一个父亲节点，求树中所有子树权值之和的期望

思路：

没啥思路 硬找规律

n = 4的情况：

发现0号点贡献了6次，6 = 3！

1号点贡献了12次，12 = 3！+ 3！/ 1

2号点贡献了15次，15 = 3！+ 3！/ 1 + 3！/ 2

3号点贡献了17次，17 = 3！+ 3！/ 1 + 3！/ 2 + 3！/ 3

于是 x 号点贡献的次数为 n! + n! / 1 + n! / 2 + ..... + n! / x

别忘了最后求的是期望，除以 n! 

#include
   
    using namespace std;typedef long long ll;const ll mod = 998244353;const double eps = 1e-11;const int N = 1e5 + 10;ll fac[N], fun[N];ll qpow(ll a, ll b) {    ll ans = 1;    a %= mod;    while(b) {        if(b & 1) ans = ans * a % mod;        a = a * a % mod;        b >>= 1;    }    return ans % mod;}void init() {    fac[0] = 1;    for(int i = 1; i < N; ++i)        fac[i] = fac[i - 1] * i % mod;    fun[0] = 1;    for(int i = 1; i < N; ++i)        fun[i] = (fun[i - 1] + qpow(i, mod - 2)) % mod;}int main() {    init();    int t, n;    ll a;    scanf("%d", &t);    while(t--) {        scanf("%d", &n);        ll ans = 0;        for(int i = 0; i < n; ++i) {            scanf("%lld", &a);            ans = (ans + fun[i] * a % mod) % mod;        }        printf("%lld\n", ans * qpow(fac[n], mod - 2) % mod * fac[n - 1] % mod);    }    return 0;}