题目描述
定义一个数列区间的 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=r⨁i=l(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