#P6900. 看节目

    ID: 6731 传统题 6000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-置换循环分解根号分块卷积转化NTT一维前缀和

看节目

题目描述

最初,第 ii 个节目在时刻 ii 举行,观看它可获得愉悦值 aia_i。

主办方使用同一个排列 pp 调整节目顺序。每次重排都将重排之前位于时刻 ii 的节目移到时刻 pip_i,所有节目同时移动。给定参数 x,yx,y,如下生成排列。

seed = x
for i = 1 to n:
    p[i] = i
    seed = (seed * y) mod 998244353
    j = seed mod i + 1
    swap(p[j], p[i])

需要处理多次重排操作和区间询问。每次区间询问求当前时刻 ll 到 rr(含端点)举行的节目愉悦值之和,对 998244353998244353 取模。

输入格式

第一行四个整数 n,m,x,yn,m,x,y,分别表示节目数、操作数及生成排列的两个参数。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,依次表示各节目的愉悦值。

接下来 mm 行,每行是一种操作。

  • 1 k:将当前节目顺序连续重排 kk 次。
  • 2 l r:查询当前时间区间 [l,r][l,r] 的愉悦值之和。

输出格式

每个类型 22 的操作输出一行一个整数,表示查询结果对 998244353998244353 取模后的值。

样例

5 5 23333 66666
1 2 1 3 8
1 1
2 2 4
2 1 3
1 2
2 2 5
5
12
14

生成的排列为 (2,5,4,3,1)(2,5,4,3,1)。第一次重排后,按时刻排列的愉悦值变为 (8,1,3,1,2)(8,1,3,1,2)。之后两次重排先得到 (2,8,1,3,1)(2,8,1,3,1),再得到 (1,2,3,1,8)(1,2,3,1,8)。

数据范围

对于全部数据,1≤n,m≤1051\le n,m\le10^5,233≤x,y<998244353233\le x,y<998244353,0≤ai<9982443530\le a_i<998244353,操作类型为 11 或 22,1≤k≤1091\le k\le10^9,1≤l≤r≤n1\le l\le r\le n。

原题数据比例 附加限制
20% n,m≤1000n,m\le1000,k≤10k\le10
40% n,m≤1000n,m\le1000
另外 10% 所有询问满足 r−l+1≤10r-l+1\le10

原题时间限制 6 秒,内存限制 512 MB。

By Mr_Spade

原 PDF 题面