# HDU-6267 Master of Random（思维、递推、概率期望）

### Master of Random

#### Time limit:1000ms Memory limit:32768kB

Hakase provides Nano with a problem. There is a rooted tree with values on nodes. For each query, you are asked to calculate the sum of the values in the subtree. However, Nano is a rookie so she decides to guess the answer. She has known how the data generator works: it identifies the nodes with labels from 0 to n − 1 and then visits them one by one. For each i (1 ≤ i ≤ n), the generator selects a node whose label is smaller than i to be its father. The pseudocode is like this:

for i = 1 to n – 1:father[i] = random(0, i – 1);
where random(a, b) randomly generates a uniformly distributed random integer in range [a, b]. Knowing n and the value of the i-th node ai, Nano decides to randomly choose a subtree and sum up all of the values in the subtree as the answer. Now Hakase wants to know what the expectation of the answer is. Can you help her?

#### Input

The first line contains an integer T (1 ≤ T ≤ 10) representing the number of test cases.
For each test case, the first line contains an integer n (1 ≤ n ≤ 100000), the number of the nodes in the rooted tree.
The second line contains n integers a0, a1, …, an−1 (1 ≤ ai ≤ 100000) represent the values of nodes.

#### Output

It can be proven that the answer equals to an irreducible fraction p/q. For each test case, print p ∗ q −1 mod 998244353 in one line. q−1 is the inverse of q under module number 998244353.

2
2
1 1
3
1 2 3

499122178
166374063

#### Explanation

The shape of the tree in the first test case is unique. The father of node 1 is 0. It is possible to choose node 0 or 1 with equal possibility. The sum of the subtree with 0 as the root is 2 while the sum of the subtree with 1 as the root is 1. So the expectation is (2 + 1)/2 = 3/2. The output is 3∗2^(−1) mod 998244353 = 400122178

#### 题意

给出n个节点的生成树，节点编号大的只能作为节点编号小的子节点，然后会生成很多随机的树，对于所有随机的树计算所有子树的所有权值的期望。

#### 思路

考虑到需要计算期望，我们可以考虑都会出现什么情况。枚举前几个会发现，n个节点的复合要求的树一共会有q=(n-1)!种生成方法，如果求出了所有树的生成的权值和p，那么我们的答案就是 。接下来的问题就是怎么求p，我们可以考虑每个节点对于答案的贡献值。
举例有4个节点的时候，画出所有的子树后，一共有6种树的生成方式。对于第一个节点来说，一共会被计算a1=6次；对于第二个节点来说，计算第一个节点的时候必定会计算上第二个节点，除此之外还有第二个节点单独被计算的情况，因此第二个节点被计算的次数为a2=2*a1=12次；对于第三个节点来说，我们可以考虑这是一个随机问题，就是说第三个节点可以出现在第一个节点下面，也可以出现在第二个节点的下面，因此出现在两个节点下面的概率都是 ，那么对于出现在第一个节点下面时会被计算a1+a1次（计算a1时和计算a3单独时），那么对于出现在第二个节点下面时会被计算a1+a2次（计算a2时和计算a3单独时），那么就有 ；对于第四个节点同理。化简之后可以得到：    。因此可以用一个数组来记录a1+a2+…，写到这里后面的做法就很简单了，递推就可以了。

#### 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const ll mod = 998244353;
const int maxn = 1e5+5;

int n;
ll fac[maxn];
ll ifac[maxn];
ll input[maxn];
ll ar[maxn];
ll br[maxn];

ll qm (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;
}

ll inv (ll k)
{
return qm(k, mod-2);
}

void init ()
{
fac = ifac = fac = ifac = 1;
for (int i = 2; i < maxn; ++i)
{
fac[i] = i*fac[i-1]%mod;
ifac[i] = inv(fac[i]);
}
}

int main ()
{
int t;
init();
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%lld", &input[i]);
}
ll q = fac[n];
ll p = 0;
ar = fac[n-1];
br = ar;
p += ar*input%mod;
p %= mod;
for (int i = 2; i <= n; ++i)
{
ar[i] = (i-1)*ar%mod+br[i-1];
ar[i] %= mod;
ar[i] *= inv(i-1);
ar[i] %= mod;
br[i] = br[i-1]+ar[i];
br[i] %= mod;
p += ar[i]*input[i]%mod;
p %= mod;
}
cout << p*inv(q)%mod << 'n';
}
return 0;
}