#P9086. 「HNOI2021 省集 Day5」序排速快

    ID: 5170 传统题 2000ms 512MiB 尝试: 4 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-冒泡排序贡献法期望线性性对称性分析线性递推

「HNOI2021 省集 Day5」序排速快

题目描述

定义一次泡冒为:

即,从该数组的第一个位置开始,设当前进行到的位置为 ii,若 Ai>Ai+1A_i > A_{i+1} 则交换。

定义一次序排速快为:

即,对于当前递归到的区间 [l,r][l, r],定义一个位置 ii 为分割点,当且仅当 ∀x∈[l,i],y∈[i+1,r],Ax<Ay\forall x \in [l, i], y \in [i + 1, r], A_x < A_y。

序排速快的过程是这样的,对于当前的区间 [l,r][l, r],若该区间长度为 11,直接返回;

否则,若该区间中存在分割点,则找出所有分割点,递归两两相邻分割点中的区间。

即,若当前递归区间为 [l,r][l,r],分割点为 p1,p2,⋯ ,pk,∀pi∈[l,r]p_1,p_2,\cdots,p_k,\forall p_i\in[l,r] 则递归 $[1,p_1],[p_1+1,p_2],\ldots,[p_{k-1}+1,p_k],[p_{k+1},r]$。

若不存在分割点,则执行多次泡冒,每一次泡冒将 cntcnt 的值加上 r−l+1r − l + 1,直至出现分割点,执行递归。

给出两个正整数 L,RL, R,对所有的 n∈[L,R]n\in[L,R] 分别求出所有长度为 nn 的排列的 cntcnt 值之和对 998244353998244353 取模的结果。

输入格式

一行两个正整数 L,RL, R,意义同题目描述。

输出格式

为减少输出量,仅输出一个整数表示所有答案的异或和。

样例

样例 1

2 8
920329

当排列长度为 22 时存在两种排列 1,21, 2,2,12, 1。

对于第一个排列,第一次递归 [1,2][1, 2] 时,分割点 1,21, 2 都已出现,则递归 [1,1],[2,2][1, 1], [2, 2],可以发现 cntcnt 的值为 00。

对于第二个排列,第一次递归 [1,2][1, 2] 时,无分割点出现,则进行一次泡冒,排列变为 1,21, 2,此时分割点 1,21, 2 均已出现,递归 [1,1],[2,2][1, 1], [2, 2], 可以发现 cntcnt 的值为 22。

故对于所有长度为 22 的排列,cntcnt 的和对 998244353998244353 取模的结果为 22。

长度为 33 时存在 66 种排列,cntcnt 的值为 1717。

长度为 66 时,cntcnt 的值为 96489648。

长度为 88 时,cntcnt 的值为 10008001000800。

样例 2,3

见选手目录下的 tros/tros*.in 和 tros/tros*.ans。

测试点约束

对于 100%100\% 的数据,2≤L,R≤1072\le L,R\le 10^7。

子任务编号 R−L+1R-L+1 RR 分值
11 ≤10\le 10 ≤8\le 8 1010
22 ≤500\le 500
33 ≤5×103\le 5\times 10^3
44 ≤105\le 10^5 2020
55 ≤106\le 10^6
66 ≤107\le 10^7 3030