#2024. 数列重排

数列重排

数列重排

题目描述

标题: 数列重排 - Problem - QOJ.ac

#4900. 数列重排

Statistics

题目描述

定义一个数列区间的 mex 为区间中最小的没有出现过的自然数,定义一个数列的价值为其中 mex≥k 的区间数量。

给定 n 个小于 m 的自然数和一个区间 [l,r],令 f(k) 表示 n 个数构成的数列所有重排列中数列价值的最大值,对于每一个 k∈[l,r],求出 f(k)。

令 ai 表示数字 i 出现的次数,保证存在正整数 X,使得 ∀i<m,ai∈{X,X+1}。

输入格式

由于 n 可能很大,将采取如下方式减少读入量:

第一行四个整数 m,l,r,X。

第二行一个长度为 m 的 01 串,若其中第 i 个位置为 1 则数字 i−1 的出现次数为 X+1,否则出现次数为 X。

根据输入可以推出 n=mX+S,其中 S 为 01 串中 1 的数量。

输出格式

为了减少输出量,令 ans=⨁i=lr(233if(i)mod998244353),其中 ⨁ 表示二进制下的按位异或,输出一行一个整数 ans。

样例输入 1

2 0 1 2
10

样例输出 1

3034

样例解释 1

在样例给出的数列中,有 3 个 0 和 2 个 1,任意排列 f(0) 均为 15,排列为 01010 时 f(1) 有最大值 13,答案为:

(2330×15mod998244353)⊕(2331×13mod998244353)=3034

样例输入 2

14 1 14 13
10110101110101

样例输出 2

379883349

数据范围

  • Subtask 1(5 points):n,m≤9。
  • Subtask 2(15 points):n,m≤200。
  • Subtask 3(15 points):n,m≤5×103。
  • Subtask 4(5 points):m≤2,l=0,r=1。
  • Subtask 5(10 points):m≤106,l=m,r=m。
  • Subtask 6(10 points):m≤106,X=1,si=0。
  • Subtask 7(15 points):m≤106,r−l+1≤104。
  • Subtask 8(15 points):m≤2×106。
  • Subtask 9(10 points):无特殊限制。

对于所有数据,满足 n≤109,m≤107,0≤l≤r≤m,X≥1。

时间限制:600ms

空间限制:256MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 0 1 2
10
3034

样例 2

14 1 14 13
10110101110101
379883349