#1787. 物理实验

    ID: 1787 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1415来源:qoj.ac数据:公开样例动态规划数学

物理实验

物理实验

题目描述

标题: 物理实验 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

物理实验室中有一个长度为 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≤1575007500M105251057500M1053101057500109141510575001091055151055×104M16151055×104M105751055×104109181010510510919101055×1041095×1041010105105109105

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 5 499122177 1 10
1 3
249561090 436731906 592707586 729186306 851042306 960712706 61476353 150964353 231884353 305069353

样例 2

5 20 704273273 100 109
7 9 13 16 17
483503804 939740408 884209216 593653317 345573406 974131468 99837503 926658164 215247850 240109650