QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 7761. 物理实验

统计

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

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

定义两个磁铁的距离为环上两个方向中距离的较小值。设 $ f_i $ 表示经过 $ i $ 个时刻之后,每一对磁铁(共 $ \frac{n(n-1)}{2} $ 对)的距离之和的期望。给定 $ L,R $,求出 $ f_L,f_{L+1},\cdots,f_R $。答案对 $ 998244353 $ 取模。

输入格式

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

第二行:$ N $ 个整数 $ x_1,x_2,\cdots,x_N $。

输出格式

一行,$ R-L+1 $ 个整数,分别表示 $ f_L,f_{L+1},\cdots,f_R $。

样例数据

样例 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\le N\le 10^5 $,$ 3\le M\le 10^5 $,$ 1<p<998244353 $,$ 1\le L\le R\le 10^9 $,$ R-L+1\le 10^5 $,$ 0\le x_i<M $。

子任务编号分值$ N\le $$ M\le $$ R\le $$ R-L+1\le $
15$ 7500 $$ 7500 $$ M $$ 10^5 $
25$ 10^5 $$ 7500 $$ M $$ 10^5 $
310$ 10^5 $$ 7500 $$ 10^9 $$ 1 $
415$ 10^5 $$ 7500 $$ 10^9 $$ 10^5 $
515$ 10^5 $$ 5\times 10^4 $$ M $$ 1 $
615$ 10^5 $$ 5\times 10^4 $$ M $$ 10^5 $
75$ 10^5 $$ 5\times 10^4 $$ 10^9 $$ 1 $
810$ 10^5 $$ 10^5 $$ 10^9 $$ 1 $
910$ 10^5 $$ 5\times 10^4 $$ 10^9 $$ 5\times 10^4 $
1010$ 10^5 $$ 10^5 $$ 10^9 $$ 10^5 $