QOJ.ac

QOJ

Time Limit: 0.6 s Memory Limit: 256 MB Total points: 100
[+2]

# 4900. 数列重排

Statistics

题目描述

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

给定 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

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

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

输出格式

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

样例输入 1

2 0 1 2
10

样例输出 1

3034

样例解释 1

在样例给出的数列中,有 3021,任意排列 f(0) 均为 15,排列为 01010f(1) 有最大值 13,答案为: (2330×15mod998244353)(2331×13mod998244353)=3034

样例输入 2

14 1 14 13
10110101110101

样例输出 2

379883349

数据范围

  • Subtask 1(5 points):n,m9
  • Subtask 2(15 points):n,m200
  • Subtask 3(15 points):n,m5×103
  • Subtask 4(5 points):m2,l=0,r=1
  • Subtask 5(10 points):m106,l=m,r=m
  • Subtask 6(10 points):m106,X=1,si=0
  • Subtask 7(15 points):m106,rl+1104
  • Subtask 8(15 points):m2×106
  • Subtask 9(10 points):无特殊限制。

对于所有数据,满足 n109,m107,0lrm,X1

时间限制:600ms

空间限制:256MB