2017ccpc杭州 D - Master of Random（hdu6267 期望 + 找规律）

 

题意：

有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<bits/stdc++.h>
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;
}