物理实验室中有一个长度为 M 的环形装置,上面放有 N 个磁铁,第 i 个磁铁在原点沿顺时针方向走 xi 个单位长度的位置上。
每经过一个时刻,每一个磁铁都会独立地以 p 的概率顺时针移动 0.5 个单位长度,以 1−p 的概率逆时针移动 0.5 个单位长度。任意时刻,如果两个磁铁的位置相同了,它们就会吸在一起(大小变化忽略不计,可等效地看成一个磁铁),之后的运动会同步(也就是以 p 的概率同时顺时针移动,以 1−p 的概率同时逆时针移动)。
定义两个磁铁的距离为环上两个方向中距离的较小值。设 fi 表示经过 i 个时刻之后,每一对磁铁(共 n(n−1)2 对)的距离之和的期望。给定 L,R,求出 fL,fL+1,⋯,fR。答案对 998244353 取模。
输入格式
第一行:五个整数 N,M,p,L,R。
第二行:N 个整数 x1,x2,⋯,xN。
输出格式
一行,R−L+1 个整数,分别表示 fL,fL+1,⋯,fR。
样例数据
样例 1 输入
2 5 499122177 1 10 1 3
样例 1 输出
249561090 436731906 592707586 729186306 851042306 960712706 61476353 150964353 231884353 305069353
样例 2 输入
5 20 704273273 100 109 7 9 13 16 17
样例 2 输出
483503804 939740408 884209216 593653317 345573406 974131468 99837503 926658164 215247850 240109650
数据范围
对于所有数据,满足 1≤N≤105,3≤M≤105,1<p<998244353,1≤L≤R≤109,R−L+1≤105,0≤xi<M。
子任务编号 | 分值 | N≤ | M≤ | R≤ | R−L+1≤ |
---|---|---|---|---|---|
1 | 5 | 7500 | 7500 | M | 105 |
2 | 5 | 105 | 7500 | M | 105 |
3 | 10 | 105 | 7500 | 109 | 1 |
4 | 15 | 105 | 7500 | 109 | 105 |
5 | 15 | 105 | 5×104 | M | 1 |
6 | 15 | 105 | 5×104 | M | 105 |
7 | 5 | 105 | 5×104 | 109 | 1 |
8 | 10 | 105 | 105 | 109 | 1 |
9 | 10 | 105 | 5×104 | 109 | 5×104 |
10 | 10 | 105 | 105 | 109 | 105 |