QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+9]
Statistics

物理实验室中有一个长度为 M 的环形装置,上面放有 N 个磁铁,第 i 个磁铁在原点沿顺时针方向走 xi 个单位长度的位置上。

每经过一个时刻,每一个磁铁都会独立地以 p 的概率顺时针移动 0.5 个单位长度,以 1p 的概率逆时针移动 0.5 个单位长度。任意时刻,如果两个磁铁的位置相同了,它们就会吸在一起(大小变化忽略不计,可等效地看成一个磁铁),之后的运动会同步(也就是以 p 的概率同时顺时针移动,以 1p 的概率同时逆时针移动)。

定义两个磁铁的距离为环上两个方向中距离的较小值。设 fi 表示经过 i 个时刻之后,每一对磁铁(共 n(n1)2 对)的距离之和的期望。给定 L,R,求出 fL,fL+1,,fR。答案对 998244353 取模。

输入格式

第一行:五个整数 N,M,p,L,R

第二行:N 个整数 x1,x2,,xN

输出格式

一行,RL+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

数据范围

对于所有数据,满足 1N1053M1051<p<9982443531LR109RL+11050xi<M

子任务编号分值NMRRL+1
1575007500M105
251057500M105
31010575001091
4151057500109105
5151055×104M1
6151055×104M105
751055×1041091
8101051051091
9101055×1041095×104
1010105105109105