猫与随机数

题目描述

Lynette 有一个长度为 $n$ 的序列 $a$，和长度为 $5$ 的序列 $T$。$q$ 次询问，给定区间 $[l,r]$ 和正整数 $i,j$，设 $a$ 在 $[l,r]$ 中的部分为序列 $b$，其长度为 $m=r-l+1$，回答以下问题：

有一条长度为 $m+2$ 的链，节点由 $0$ 到 $m+1$ 标号，定义一次从 $i$（$i\in[1,m]$）开始的随机游走过程为：

• 设当前点为 $u$。
• 若 $u\in\{0,m+1\}$，则停止。
• 否则将费用加上 $b_u$，并且以相同的概率走到 $u-1$ 或 $u+1$。

回答以下问题（均对 $998244353$ 取模）：

1. 从 $i$ 开始随机游走，结束时 $u=0$ 的概率。
2. 从 $i$ 开始随机游走，经过 $j$ 的期望次数。
3. 从 $i$ 开始随机游走，期望费用。
4. 从 $[1,m]$ 的所有点开始随机游走，经过 $j$ 的期望次数和。
5. 从 $[1,m]$ 的所有点开始随机游走，期望费用和。

注意：初始的点也要算次数和费用。

设以上五个问题的答案为 $r_1,r_2,r_3,r_4,r_5$，你需要回答 $\sum_{i=1}^{5}r_iT_i$，这个求和不用取模。

为了避免输入输出量过大，本题采用特殊的输入输出方式。

输入格式

复制以下代码（或者在下发文件 input.cpp 中复制）：

namespace Input{
    std::mt19937_64 R;
    std::uniform_int_distribution<int> D, D1;
    inline void init(int n, int m, int seed){
        R = std::mt19937_64(seed);
        D = std::uniform_int_distribution<int>(1, n);
        D1 = std::uniform_int_distribution<int>(1, m);
    }
    inline int get(){
        return D1(R);
    }
    inline void get(int &l,int &r, int &i, int &j){
        l = D(R), r = D(R), i = D(R), j = D(R);
        if(l > r) std::swap(l, r);
        if(i < l) std::swap(l, i);
        if(i > r) std::swap(i, r);
        if(j < l) std::swap(l, j);
        if(j > r) std::swap(j, r);
        if(R() & 1) std::swap(i, j);
        i -= l - 1;
        j -= l - 1;
    }
}
using Input::init;
using Input::get;

第一行 $4$ 个整数 $n,m,q,seed$，分别表示序列长度、$a_i$ 的上限、询问次数以及随机数种子。

第二行 $5$ 个整数，分别表示 $T_1,T_2,T_3,T_4,T_5$。

在读完上面数据之后，调用 init(n, m, seed)。

接下来调用 $n$ 次 get() 函数，第 $i$ 次调用的返回值是 $a_i$。

接下来调用 $q$ 次 get(l, r, i, j) 函数，获得一次询问的参数。

输出格式

设第 $i$ 次的答案为 $ans_i$，输出一行一个整数表示 $\bigoplus_{i=1}^{q}(i\times ans_i)$，这里不需要取模。

样例 1 输入

5 5 3 998244353
0 1 1 0 1

样例 1 输出

1283457144

样例 1 说明

$a$ 序列为 $[4,3,5,3,3]$，三次询问及其对应的 $r_2,r_3,r_5$ 分别为：

• $l=1,r=2,i=2,j=2,r_2=332748119,r_3=665496242,r_5=14$。
• $l=1,r=4,i=2,j=3,r_2=798595484,r_3=199648893,r_5=76$。
• $l=1,r=3,i=2,j=1,r_2=1,r_3=15,r_5=39$。

数据范围

对于所有数据，$1\le n,q\le5\times10^6$，$1\le m\le998244352$，$1\le a_i\le m$，$1\le l\le r\le n$，$1\le i,j\le r-l+1$，$0\le T_i\le1$，$1\le seed<2^{30}$。

子任务

本题采用捆绑测试，并开启所有合理的子任务依赖。