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.

Example

standard input

2
2
1 1
3
1 2 3

standard output

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,那么我们的答案就是\frac{p}{q}。接下来的问题就是怎么求p,我们可以考虑每个节点对于答案的贡献值。
        举例有4个节点的时候,画出所有的子树后,一共有6种树的生成方式。对于第一个节点来说,一共会被计算a1=6次;对于第二个节点来说,计算第一个节点的时候必定会计算上第二个节点,除此之外还有第二个节点单独被计算的情况,因此第二个节点被计算的次数为a2=2*a1=12次;对于第三个节点来说,我们可以考虑这是一个随机问题,就是说第三个节点可以出现在第一个节点下面,也可以出现在第二个节点的下面,因此出现在两个节点下面的概率都是\frac{1}{2},那么对于出现在第一个节点下面时会被计算a1+a1次(计算a1时和计算a3单独时),那么对于出现在第二个节点下面时会被计算a1+a2次(计算a2时和计算a3单独时),那么就有a3=\frac{1}{2}*(a1+a1)+\frac{1}{2}*(a1+a2);对于第四个节点同理。化简之后可以得到:a1=(n-1)!a2=2*a1a3=\frac{1}{2}*(3*a1+a2)a4=\frac{1}{3}*(4*a1+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[0] = ifac[0] = fac[1] = ifac[1] = 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[1] = fac[n-1];
        br[1] = ar[1];
        p += ar[1]*input[1]%mod;
        p %= mod;
        for (int i = 2; i <= n; ++i)
        {
            ar[i] = (i-1)*ar[1]%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;
}

发表评论